Longest Common Prefix

题目描述

Write a function to find the longest common prefix string amongst an array of strings.
找到一个字符串数组中所有字符串的最长公共前缀。

解题思路

动态规划。
一个一个去找。

代码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";
        if (strs.length == 1)
            return strs[0];
        String ret = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int min = ret.length();
            if (min > strs[i].length()) {
                min = strs[i].length();
                ret = ret.substring(0, min);
            }
            for (int j = 0; j < min; j++) {
                if (ret.charAt(j) != strs[i].charAt(j)) {
                    if (j == 0)
                        return "";
                    else
                        ret = ret.substring(0, j);
                    break;
                }
            }
        }
        return ret;
    }
}