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

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.

分析：在一个字符串数组中找到最长的字符串前缀，注意是前缀呢。比如“flower”中“fl”可以是一个前缀，但是“low”就不是前缀。之前我在这里就犯错了，以为是出现最多的字符串即可呢。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String res = "";
        if(strs.length == 0){
            return res;
        }
        String shortStr = strs[0];
        int n = strs[0].length();
        // 找到字符串数组中最短的字符串
        for (String str : strs) {
            if (str.length() < n) {
                n = str.length();
                shortStr = str;
            }
        }

        for (int i = n; i > 0; i--) {
            int count = 0;
            String sub = shortStr.substring(0, i);
            // 遍历字符串数组，判断该子字符串是否都存在各个字符串中（保证得是前缀）
            for (String str : strs) {
                if (sub.equals(str.substring(0, i))) {
                    count++;
                }
                if (count == strs.length) {
                    res = sub;
                    return res;
                }
            }
        }
        return res;
    }
}