LeetCode: 14. Longest Common Prefix

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

?

大意就是，寫一個函數可以找到一個數組字符串中的最長前綴。

?

分析： 最長前綴的最大值為數組字符串中長度最短的字符，由最短字符串由后向前遞減可以得到最長前綴。

?

算法構架：先遍歷求得最短字符串和長度n，然后再次遍歷數組，用最短字符串依次對比當前字符串前n個字符是否相等，不相等則n--，直到找到最短字符串和當前字符串前n個字符相等，繼續遍歷。

注意：因為是求共有的前綴，所以前綴必定滿足所有字符串，因此只用單次遍歷數組即可以求得答案。

?

public class Solution 
{public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0){return "";}int length = strs[0].length();String res = strs[0];for (int i = 1; i < strs.length; i++){if (strs[i].length() < length){length = strs[i].length();res = strs[i];}}for (String s : strs){while (!res.equals(s.substring(0,length))){length--;res = res.substring(0,length);}}return res;}
}

復雜度為n