Java 中字符串数组中的最长公共前缀

Question

我正在尝试使用 java 在字符串数组中找到最长的公共前缀。以下是我的解决方案，但是当我将它上传到 leetcode 时，它失败了，我不明白哪个测试用例失败了。我测试的所有测试用例都工作正常。

我的方法是匹配字符串数组中所有单词的第一个字符，如果所有单词都有相似的第一个字符，那么它移动到第二个字符，否则函数 returns 字符串。

如果有人帮我找出我的代码失败的测试用例，我将不胜感激。以下是我写的代码：

public static String LongCommonPrefix(String[] strs)
    {
        String commonPrefix="";
        int count=0, k=0;
        
        if(strs.length>0)
        {
            for(int i=0; i<strs[0].length(); i++)
            {
                int j=1;
                while(j<strs.length)
                {
                    if(strs[0].charAt(k)==strs[j].charAt(k))
                    {
                        count++;
                        j++;
                    }
                    else
                        break;
                }
                if(count==strs.length-1)
                {
                    commonPrefix+=strs[0].charAt(k);
                    count=0;
                    k++;

                }
                else
                {
                    return commonPrefix;
                }

            }
        }

        return commonPrefix;
    }

Answer 1

您的代码中的错误在于您使用的部分没有检查变量 (K) 是否可能大于数组的字符串长度 (j)。要解决这个问题，在使用变量（K）之前添加一个条件语句就可以了。祝你好运

Answer 2

试试这个方法。

public static String longestCommonPrefix(String[] s) {
    if (s.length == 0) return "";
    
    String prefix = s[0];
    for (int i = 1; i < s.length; i++) {
        while (s[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.equals("")) return "";
        }
    }
    return prefix;
}

我已经检查过：

String[] arr = {"giorgi", "gio", "gior", "giorg", "gior"};
System.out.println(longestCommonPrefix(arr));

它通过打印 gio.

完成了这项工作

Answer 3

试试这个：

private static String findPrefix(String[] prefixes) {
        String res = "";

        if (prefixes.length == 0) return res;

        for (int i = 0; i < prefixes.length; i++) {
            char[] chars1 = prefixes[i].toCharArray();

            for (int j = i+1; j < prefixes.length; j++) {
                //break if itself
                if (i == j) continue;
                char[] charsMatch = null;
                char[] chars2 = prefixes[j].toCharArray();

                if (chars1.length > chars2.length) {
                    for (int y = 0; y < chars2.length; y++) {
                        if (chars2[y] == chars1[y]) {
                            if (charsMatch == null) {
                                charsMatch = new char[chars2.length];
                            }
                            charsMatch[y] = chars1[y];
                        }
                    }
                } else {
                    for (int y = 0; y < chars1.length; y++) {
                        if (chars2[y] == chars1[y]) {
                            if (charsMatch == null) {
                                charsMatch = new char[chars1.length];
                            }
                            charsMatch[y] = chars1[y];
                        }
                    }
                }

                if (charsMatch != null && res.length() < charsMatch.length) {
                    res = new String(charsMatch);
                }
            }
        }

        return res;
    }

Java 中字符串数组中的最长公共前缀

Longest Common Prefix in String Array in Java

java

arrays

string

character

prefix