問題
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: ["flower","flow","flight"] Output: "fl"
Example 2:
Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.
https://leetcode.com/problems/longest-common-prefix/
Note: All given inputs are in lowercase letters a-z.
自分の解答1
public String longestCommonPrefix(String[] strs) { if (strs.length == 0) { return ""; } int strsLength = strs.length; int minLength = strs[0].length(); int minLengthIndex = 0; String minLengthWord = strs[0]; for (int i = 1; i < strsLength; i++) { if (strs[i].length() < minLength) { minLength = strs[i].length(); minLengthIndex = i; minLengthWord = strs[i]; } } for (int i = minLengthWord.length(); i > 0; i--) { String commonPrefix = minLengthWord.substring(0, i); boolean isCommonPrefix = true; for (int m = 0; m < strsLength; m++) { if (m == minLengthIndex) { continue; } if (!strs[m].startsWith(commonPrefix)) { isCommonPrefix = false; break; } } if (isCommonPrefix) { return commonPrefix; } } return ""; }
コード理解
別解 Horizontal scanning
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); if (prefix.isEmpty()) return ""; } return prefix; }
Time : O(S) where S is the sum of all characters in all strings.
Space : O(1)
別解 Vertical scanning
public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return ""; for (int i = 0; i < strs[0].length() ; i++){ char c = strs[0].charAt(i); for (int j = 1; j < strs.length; j ++) { if (i == strs[j].length() || strs[j].charAt(i) != c) return strs[0].substring(0, i); } } return strs[0]; }
あとは、Divide and conquer(分割統治)やBinary search(二分探索)など。
Stringの比較は、例えば dog
とcat
を比較するとき、1文字ずつ合計3回の比較が必要となる。
自分のロジックは、例えば ["cat", "cartoon", "cleen"]とあった場合、一番短いcatと他の2つを比較し、ヒットしなかったら次はca、最後にcと比較していくが、これではcだけ見ても6回比較することになってしまう。これが無駄なポイント。 Horizontal Search含め全て1回しか見ないような工夫がされている。
今後のための考え方
- 複数の文字列を比較するときは、同じ文字の比較は1回ずつで済むようなロジックを書く
- All given inputs are in lowercase letters a-z.と言われてもそもそもinputsが無い場合もあるからそれもケアすべし