14.LongestCommonPrefix.md

14. Longest Common Prefix

Question:

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.

Thinking:

• Method1:We find need to find the longest prefix, so we compare every two strings and get the longest prefix, after iterating all of the String array, we will get the answer.

	class Solution {
	    public String longestCommonPrefix(String[] strs) {
	        if(0 == strs.length) return "";		//Check the boundary conditions.
	        if(strs[0].length() == 0) return "";
	        String result = strs[0];
	        for(int i = 1; i < strs.length; i++){
	            if(strs[i].equals("")) return "";
	            int len = Math.min(result.length(), strs[i].length());	//Compare current result and next String.
	            result = result.substring(0, len);
	            for(int j = 0; j < len; j++){
	                if(result.charAt(j) != strs[i].charAt(j)){
	                    result = result.substring(0, j);
	                    break;
	                }
	            }
	        }
	        return result;
	    }
	}

二刷

• 我们只需要找出两个的prefix，再用该prefix一直向后遍历找出短的可能。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0) return "";
        if(strs.length == 1) return strs[0];
        String result = commonPrefix(strs[0], strs[1]);
        for(int i = 2; i < strs.length; i++){
            result = commonPrefix(result, strs[i]);
        }
        return result;
    }
    private String commonPrefix(String s1, String s2){
        if(s1 == null || s2 == null) return "";
        int len = s1.length();
        for(int i = len; i >= 0; i--){
            String prefix = s1.substring(0, i);
            if(s2.startsWith(prefix)) return prefix;
        }
        return "";
    }
}