[📝LeetCode #14] Longest Common Prefix

🎀 The Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example:

Input: strs = ["flower","flow","flight"]
Output: "fl"

👩‍💻 My Answer

class Solution { public String longestCommonPrefix(String[] strs) { if (strs.length < 2) return strs[0]; String word = strs[0]; String output = ""; Boolean check = false; for (int i = 1; i < strs.length; i++) { String word2 = strs[i]; if (i % 2 == 0) { check = true; word = ""; } else if (i % 2 == 1) { check = false; output = ""; } if (!check) { for (int j = 0; j < Math.min(word.length(), word2.length()); j++) { if (word.charAt(j) == word2.charAt(j)) output += word.charAt(j); else break; } } else { for (int j = 0; j < Math.min(output.length(), word2.length()); j++) { if (output.charAt(j) == word2.charAt(j)) word += output.charAt(j); else break; } } } if (!check) return output; return word; } } 

Pro & Con

• ✖️ Runtime & Memory (OMG it's so slow)
• ✖️ Too long
• ✖️ Bit complicated (Hard to read)

💋 Ideal Answer

Approach - "Two Pointer"

I read the solution post on LeetCode and found the two approaches. I will explain by using the example:

Input: strs = ["flower","flow","flight"]
Output: "fl"

One approach is:
Set the prefix = first word, so "flower"
Compare the prefix("flower") and next word("flow")
If charAt differs, it substrings to that index (prefix.substring(0, index))

Another one is:
Set the prefix = first word, so "flower"
Use strs[i].indexOf(prefix) to see if strs[i] contains prefix or not.
If not, it reduces the last char of prefix (prefix.substring(0,prefix.length()-1))

I tried both and found that the second one is much faster(Beat 100%) than the first one (Beat 64%). The reason is the first one uses nested loop (SUPER inefficient) while the second one uses indexOf(), which is a highly optimized native method in java!

Here is the second method code:

New Code

class Solution { public String longestCommonPrefix(String[] strs) { String prefix = strs[0]; for (int i = 1; i < strs.length; i++) { while(strs[i].indexOf(prefix) != 0){ prefix=prefix.substring(0,prefix.length()-1); } } return prefix; } } 

💡 What I Learned

• Set the prefix = first word. (Learn a better algorithm)

• Avoid nested loops at all costs!