(Java Greedy) 문자열안에 포함된 가장 긴 팰린드롬(palindrome)문자열

---

(Java / 거꾸로해도 같은 문자열 / 팰린드롬(palindrome) )

문제

거꾸로해도 같은 문자열을 팰린드롬(palindrome) 이라고 한단다.

문자열이 주어지면 그안에 포함된 가장 긴 팰린드롬 문자열의 길이가 몇인지 구하는 알고리즘

ex) "dkwqabcdcbawp" 면 7을 반환 / "abba" 면 4를 반환

풀이를 보지않고 풀어서 정확한지는 모르겠지만 내가 푼 방식은

1. input(주어진 문자열)을 거꾸로 뒤집은 문자열을 만든다. (reverse)

 String input = "xxxabbbaoowla" -> String reverse = "alwooabbbaxxx"

2. input과 reverse에 같은 내용을 포함하는 가장 긴부분을 찾는다.

String input = "xxxabbbaoowla" -> String reverse = "alwooabbbaxxx"

3. 먼저 input의 0 ~ 2 문자열을 reverse에 포함되어있는지 보고 포함되지 않았다면 1~3 문자열로 다시 검사한다.

만약 포함되는 문자가 나왔으면 max를 2로 하고 반복을 종료한 후, 길이를 늘려 0~3 문자열이 reverse에 포함되었는지 검사.

설명을 적어놓고보니 greedy 접근방법이 아닌것 같다.

이 순회방식을 긴것부터 줄여가면서 포함여부를 확인하면 greedy가 될것같은 느낌이다.

      String input = "dkwqabcdcbawp";
      String reverse = "";

//    리버스 생성
      for(int i= input.length()-1; i >= 0; i--){
         reverse += input.charAt(i);
      }

      System.out.println(input);
      System.out.println(reverse);
      System.out.println("======================");

//    리버스가 포함하는 가장긴 문자열 찾기
      int max = 1;
      for(int i = 2; i <= input.length() ;i++){
         for(int j = 0; j <= input.length() - i; j++){
            if(reverse.contains(input.substring( j, j+i))){
               max = i;
               break;
            }
         }
      }
      System.out.println(max);

---

* 추가

public static void main(String[] args) {

      String input = "xxxabbbaoowla";
      System.out.println(solve(input));

   }

   public static int solve(String input){

      String reverse = "";

      for(int i= input.length()-1; i >= 0; i--){
         reverse += input.charAt(i);
      }

      System.out.println(input);
      System.out.println(reverse);
      System.out.println("======================");

//    가장긴 리버스가 같은 문자열 고르기
      int max = 1;
      for(int i = input.length(); i > 1 ; i--){
         for(int j = 0; j <= input.length() - i; j++){
            if(reverse.contains(input.substring( j, i+j))){
               max = i;
               return max;
            }
         }
      }
      return max;
   }