[📝LeetCode #14] Longest Common Prefix

#leetcode #java #100daysofcode #string

🎀 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!

DEV Community