하위 문자열 인덱스가 범위를 벗어났습니다.

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++)으로 내부 루프를 변경하십시오.

프로그램이 있기 때문에 당신의 외부 루프의 두 번째 반복에서 바운드 예외 당신을주고, 당신의 나는 일이되고 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를 만듦으로써 문제가 해결되었습니다.

길이가 변경된 것을 볼 수 없으며 이는 코드에서 또 다른 오류입니다. 답변이 업데이트되면 길이를 답변의 길이로 변경해야합니다. 이것에 대한 간단한 수정은 두 번째 "if"문에서 length = subStr.length()를 만드는 것입니다.

알고리즘은 O (n^3)의 복잡도로 실행되므로 여전히 빠르지 않습니다.

Answer 3

0에서 s.length-1까지 반복하지 않아야합니까?

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

하고 확실히 아웃 오브 바운드 인덱스가 발생할 수 있습니다 일을하지

J와 다음 루프에 대한 비슷한 일을 : 루프 조건이 될 의미 .

Answer 4

루프 상태를 변경해야합니다. <이 아닌 <이어야합니다. 'babad'의 길이를 확인하면 5가 나오지만 0부터 시작하여 4에서 끝납니다. 따라서 루프 상태를 변경해야하며 문제가 해결됩니다. 문제의