LeetCode: Longest Common Prefix

問題

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 "".

解答

大して上手いやり方が思い当たらず、力任せに解くことにしました。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        StringBuilder sb = new StringBuilder("");
        char currentChar = 0;
        for (int i = 0; ; i++) {
              for (int j = 0; j < strs.length; j++) {
                  String str = strs[j];
                  if (str.length() <= i) {
                    return sb.toString();
                  }
                  char ch = str.charAt(i);
                  if (j == 0) {
                    currentChar = ch;
                  }
                  if (ch != currentChar) {
                    return sb.toString();
                  }
             }
        sb.append(currentChar);
        }
    }
}

入力される配列のサイズをm、文字列の平均長をnとすると、

時間計算量：O(m x n)、メモリ計算量：O(n)

グラフを見た感じも他の人も同じような戦略のようですね。

他の人の解答も見てみましょう。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        
        if(strs.length == 0 || strs == null)
        {
            return "";
        }
        
        String longCommonPre = strs[0];
        for(int i = 1;i<strs.length;i++)
        {
            int k = 0;
            String currentItem = strs[i];
            while(k < longCommonPre.length() && k < currentItem.length() && longCommonPre.charAt(k) == currentItem.charAt(k))
            {
                k++;
                
            }
            if( k == 0)
            {
                return "";
            }
            longCommonPre = longCommonPre.substring(0,k);
        }
        
        return longCommonPre;
    }
}

時間計算量：O(m x n)、メモリ計算量：O(n)

やっていることは同じですが、僕のコードの方がわかりやすくないですか？