部分文字列の範囲外

Question

文字列の中で最も長い回文を見つける簡単なプログラムを書いています。私がやっていることは、各部分文字列が回文であるかどうかを調べて、長さを調べることです。長さが前の長さよりも長い場合、私は新しい最長の部分文字列を持っています。たとえば、 "babad"は "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

パートA - 他の人が指摘したようにコンパイラエラー

1. はfor(int i = 0;i<=s.length();i++)からfor(int i = 0;i<s.length();i++)にあなたの外側のループを変更します。
2. 内側ループをfor(int j = 0; j<= s.length();j++)からfor(int j = i; j< s.length();j++)に変更します。

あなたのプログラムが原因で、あなたの外側のループの2回目の繰り返しにバインドされた例外のあなたを与えている、あなたの私は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()); 
} 

追加のヘルプが必要な場合はお知らせください。

Answer 2

私のコードのエラーは、コメントの人の中にはi> jと指摘されていることが分かりました。したがって、回文を検索するときにj = iとするだけで問題が解決されました。

また、長さの変更が表示されないことがわかります。これはコード内の別のエラーです。答えが更新されたら、長さは答えの長さに変更する必要があります。このための単純な修正は、2番目のif文でlength = subStr.length（）を行うことです。

アルゴリズムはO（n^3）の複雑さで実行されるため、まだ高速ではありません。

Answer 3

0からs.length-1まで繰り返すべきではありませんか？

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

、それは確かに範囲外のインデックスにつながる可能性がやっていない

jを持つ次のforループ同様のものを：あなたループ条件があることを意味するであろう 。

Answer 4

ループ条件を変更する必要があります。 <ではなく、<でなければなりません。なぜなら、あなたが 'babad'の長さをチェックすると、あなたに5が与えられますが、インデックスは0から始まり、4で終わります。ループの状態を変更する必要があり、問題が解決されます。問題の