[アルゴリズム]クエリーの検索-java

回文とは何ですか.

題

回文創意

コード

1.返事とは何ですか.
回文は逆さまに読んでも読める文や単語です.定例公務

蘇州万瓶湾住所

雁、トマト

2.質問
私が受け取った問題は、文にパラメータが与えられたときに、文の中で最も長い返事を返す解答を書くことです.
ex)
1) aba -> aba
2) aa -> aa
3) a -> a
4)aaabbb->aaaaaまたはbbb
3.返事を探す
最初は、パラメータの長さですべての単語を検索して、一番長い単語から返事かどうかを検証したいのですが、時間が長すぎるかもしれないのでスキップしました.
そして効率を高めるために、問題を解決する方法を考え出しました.回文の中に中を見つけて、真ん中から左に1文字、右に1文字移動すれば、回文の長さを増やすことで確認できます.このように回文を現在最も長い回文と比較し,長い場合は置き換え,短い場合はそのままスキップする.例を挙げて説明する.
1)会議の中心を探す
例文の中心は「aa」または「aba」で、2つまたは3つの字で始まる.「aba」では、回文の中心は「b」と見なすことができますが、一字だけで中心であることを知ることはできませんので、左右は同じものを探します.
2)回文中心の左右に1文字ずつ比較する
入力したパラメータが「oxabxy」の場合
回文の中心は「aba」です.ここで左の字は「x」、右の字も「x」です.次の左の字は「o」、右の字は「y」です.では、回文は「xbax」であり、初期値に設定された回文値と長さを比較します.このとき,初期値は字の最初の字とする.
文字を読むだけでは煩わしくて分かりにくい.次のコードを作成します.

public String solution(String s) {
	// 초기값으로 파라미터의 첫번째 문자를 입력한다.
       String answer = String.valueOf(s.charAt(0));
       String palindrome = "";
       char[] chars = s.toCharArray();
       int initPalindromeLen =0;
       // 1. 회문의 중심을 찾는다.
       // 1-1. 이때 회문 중심의 길이는 2 또는 3이다.
       // 2. 중심부에서 왼쪽, 오른쪽으로 한칸씩 확인하면서 확장
       for(int i=0; i< s.length()-1;i++){
           // 시작 회문의 길이가 3인 경우 ex) aba
           int left = 0;
           int right = 0;
           if(i+2 <= s.length()-1&&chars[i]==chars[i+2]){
               left = i;
               right = i+2;
               initPalindromeLen = 3;
               palindrome = s.substring(left,right+1);
               palindrome = check(palindrome,chars,left,right);

           }
           if(answer.length() < palindrome.length()) answer = palindrome;

           // 시작 회문의 길이가 2인 경우 ex) aa
           if(chars[i] ==chars[i+1]){
               left = i;
               right = i+1;
               initPalindromeLen = 2;
               palindrome = s.substring(left,right+1);
               palindrome = check(palindrome,chars,left,right);

           }
           if(answer.length() < palindrome.length()) answer = palindrome;
       }
       System.out.println(s +":"+answer);
       return answer;
   }

   // 회문 확인하기 -> 왼쪽과 오른쪽 각각 한자리씩 이동하면서 동일한지 검사한다.
   private String check(String initPalindromeLen, char[] chars, int left, int right){

       while(left-1>=0 && right+1<=chars.length-1 && chars[left] == chars[right]){
           left-=1;
           right+=1;
           if(chars[left] == chars[right]){
               initPalindromeLen = chars[left]+initPalindromeLen+chars[right];
           }else {
               break;
           }
       }

       return initPalindromeLen;
   }