PattySung

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 1:

Input: strs = [“flower”,“flow”,“flight”] Output: “fl” Example 2:

Input: strs = [“dog”,“racecar”,“car”] Output: "" Explanation: There is no common prefix among the input strings.

<解題>

strs[i].indexOf(prefix) != 0 表示在字符串 strs[i] 中尋找 prefix 字串的索引位置，如果索引位置不等於 0，則表示 prefix 不是 strs[i] 的前綴。

具體來說：

如果 indexOf(prefix) 返回 0，這意味著 prefix 是 strs[i] 的前綴，因為字串索引是從 0 開始的，而 0 表示字串的開頭。如果 indexOf(prefix) 返回的索引位置大於 0，那麼 prefix 出現在 strs[i] 的某個位置，但不是在開頭，因此不是前綴。如果 indexOf(prefix) 返回 -1，這意味著 prefix 不存在於 strs[i] 中。


class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        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;
    }
}

Time: O(n) Space: O(1)

Leetcode-14. Longest Common Prefix

<解題>