子串索引越界

Question

我正在编写一个简单的程序来查找字符串中最长的回文。我正在做的是检查每个子串是否是回文，然后检查它的长度。如果长度大于之前的长度，那么我就有了新的最长子串。例如，"babad"、return、"bab" 或 "aba" 都可以。但我的问题是我的子字符串调用的索引超出范围，我不知道为什么。

public class LongestPal{
    public static void main(String[] args)
    {
        String test = new String("babad");
        String result = longestPalindrome(test);

    }
    public static String longestPalindrome(String s) {
        int length = 0;
        String answer = new String();

        for(int i = 0;i<=s.length();i++)
        {
            for(int j = 0; j<= s.length();j++)
            {
                String subStr = s.substring(i,j); // Get all substrings
                System.out.println(subStr); // Checking to see if all are printed

                boolean result = isPalindrome(subStr); //Check for palindrome
                if(result)
                {
                    if(length < subStr.length()) //If length of new substr is greater than the old one, 
                                                //the new answer will be longer substring
                    {
                        answer = subStr;   
                    }
                }
            }
        }
        return answer;
    }
    public static boolean isPalindrome(String s) //Recursive palindrome checker
    {
        if(s.length() == 0 || s.length() == 1)
            return true; 
        if(s.charAt(0) == s.charAt(s.length()-1))
            return isPalindrome(s.substring(1, s.length()-1));
        return false;
    }
}

当我打印出来的时候，我得到了所有的子串组合，直到"babbad"之后才出现错误。

Answer 1

所以我的代码中的错误原来是当 i>j 时，正如评论中的一些人所指出的那样。因此，在搜索回文时简单地使 j=i 就解决了这个问题。

您还会注意到您从未看到长度发生变化，这是代码中的另一个错误。答案更新后，必须将长度更改为答案的长度。一个简单的解决方法是在第二个 "if" 语句中设置 length = subStr.length()。

该算法仍然不快，因为它运行复杂度为 O(n^3)。

Answer 2

你不应该从 0 迭代到 s.length-1 吗？这意味着你的循环条件是：

for(int i = 0;i<s.length();i++)

下一个循环的类似循环 j

不这样做肯定会导致索引越界。

Answer 3

您需要更改循环条件。它应该只是 < 而不是 <=。因为如果你检查 'babad' 的长度，它会给你 5 但索引从 0 开始到 4 结束。所以你需要改变循环条件，它会解决问题。

Answer 4

问题的 A 部分 - 编译器错误

正如其他人指出的那样，将您的外循环从 for(int i = 0;i<=s.length();i++) 更改为 for(int i = 0;i<s.length();i++)。
将您的内部循环从 for(int j = 0; j<= s.length();j++) 更改为 for(int j = i; j< s.length();j++)。

你的程序给了你越界异常，因为在你的外循环的第二次迭代中，你的 i 变成了 1 而 j 从 0 开始。然后你调用字符串的子字符串方法 s.substring(1,0); 这显然给你这个例外。

按照建议进行更正，然后继续。如果您需要更多帮助，请告诉我们。

问题的 B 部分 - 更快的算法

这是一个更高效的算法。我相信这也应该是最快的。

    public static void main(String[] args) {        
    String s = "babad";

    int starter = 0;

    if(s.length() % 2 == 0) 
        starter = 1;

    String answer = "";
    Boolean found = Boolean.FALSE;
    while(starter < s.length() - 1) {
        for(int i=0; i<=starter; i++) {
            if(isPelindrom(answer = s.substring(i, i+ s.length() - starter))) {
                found = Boolean.TRUE;
                break;
            }
        }
        if(found) break;
        starter = starter + 1;          
    }
    if(!found) answer = String.valueOf(s.charAt(0));
    System.out.println("The answer is " + answer);

}

public static Boolean isPelindrom(String s) {
    return s.equalsIgnoreCase(new StringBuilder(s).reverse().toString());
}

如果您需要其他帮助，请告诉我。

子串索引越界

Substring index out of bounds

java

substring

palindrome