leetcode-最长公共前缀

这是我参与8月更文挑战的第5天，活动详情查看：8月更文挑战

今天例会发现都周四了。How time flys
本周成果不多，代码也没写多少，从只解决一个非常具体的问题怎么做，到需要主导做什么，还是没完全转变过来。不过觉得痛苦，就是在成长，只能暂且先这么安慰自己吧。

继续挑战leetcode第14提，连续刷了2天水题，发现的今天更水了。。。

题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：
输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

示例 2：
输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

思路

暴力一个个比较下来就可以了，思路也没什么需要画图才能说明白的，按照位数，先比较第1位，再比较第2位，直到出现某一位不一样为止。唯一需要注意的一点是，不要超出任何一个字符串的长度，避免溢出。
后来仔细思考了一下，为什么这样的题目会出现在leetcode，其实可能还是有点编程思想在里面，这题很简单，但是也可以用来解释一些非常常用的编程思想。跟求最大公约数非常类似的是，可以递归求值：f(a,b,c,d) = f(a,f(b,f(c,d)))；也可以分治：f(a,b,c,d) = f(f(a,b),f(c,d))。
强行解释了一波，也很可能只是让你练练手，熟悉一下代码怎么写而已。

Java版本代码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        StringBuilder ans = new StringBuilder();
        String strFirst = strs[0];
        int index = 0;
        int len = strFirst.length();
        while (index < len) {
            char c = strFirst.charAt(index);
            boolean breakFlag = false;
            for (int i = 1; i < strs.length; i++) {
                String item = strs[i];
                if (item.length() == index) {
                    breakFlag = true;
                    break;
                }
                char citem = item.charAt(index);
                if (c != citem) {
                    breakFlag = true;
                    break;
                }
            }
            if (breakFlag) {
                break;
            }
            ans.append(c);
            index++;
        }
        return ans.toString();
    }
}
复制代码