LeetCode 14.最长公共前缀

Question

题：

编写一个函数来查找字符串数组中最长的公共前缀字符串。如果没有公共前缀，则返回空字符串“”。

例1：

输入：[“花”，“流”，“飞行”] 输出：“fl”

例2：

输入：[“dog”，“racecar”，“car”] 输出：“”

说明：输入字符串中没有公共前缀。

码：

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

这是第二种解决方案，但我不理解内循环。我认为如果strs中的第二个元素返回一个字符串并结束for循环，则第三个元素将没有机会进行比较。

Answer 1

你的第一个循环是在第一个数组字符串中的所有字符上进行迭代。第二个循环是检查所有字符串数组的i posis的char。如果字符不匹配，或者字符串的长度与i相同，则返回子字符串结果。

我认为最好的理解方法是调试这个例子。

Answer 2

如果第二个字符串中的char与第一个字符串中的char不同，则返回是正确的，因为这意味着公共前缀在那里结束。不需要检查第三个和后面的字符串。

基本上它会在找到不匹配的字符后立即返回。

Answer 3

你必须检查所有单词中的相同位置，然后进行比较。

         positions
word    0 1 2 3 4 5
=====================
w[0]    F L O W E R
w[1]    F L O W
w[2]    F L I G H T

在Java中：

class Main {

    public static void main(String[] args) {
        String[] words = {"dog","racecar","car"};

        String prefix = commonPrefix(words);

        System.out.println(prefix);
        // return empty string

        String[] words2 = {"dog","racecar","car"};

        String prefix2 = commonPrefix(words2);

        System.out.println(prefix2);
        // Return "fl" (2 letters)
    }

    private static String commonPrefix(String[] words) {
        // Common letter counter
        int counter = 0;

        external:
        for (int i = 0; i < words[0].length(); i++) {

            // Get letter from first word
            char letter = words[0].charAt(i);

            // Check rest of the words on that same positions
            for (int j = 1; j < words.length; j++) {
                // Break when word is shorter or letter is different
                if (words[j].length() <= i || letter != words[j].charAt(i)) {
                    break external;
                }
            }

            // Increase counter, because all of words
            // has the same letter (e.g. "E") on the same position (e.g. position "5")
            counter++;
        }

        // Return proper substring
        return words[0].substring(0, counter);
    }

}