leetcode 5. Longest Palindromic Substring 풀이

 

leetcode 5번문제 풀이를 해보도록 하겠습니다.

 

문제. 

[요약]

- 주어진 문자열에서 최대 길이를 갖는 문자열을 리턴해라.

-회문은 앞에서 부터 읽든, 뒤에서부터 읽든 동일한 문자열.

 

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd" Output: "bb"

Example 3:

Input: s = "a" Output: "a"

Example 4:

Input: s = "ac" Output: "a"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

class Solution {
    public String longestPalindrome(String s) {
        String maxStr = "";
        for (int i = 0; i < s.length(); i++) {
          String str1 = checkPalind(s, i, i);
          String str2 = checkPalind(s, i, i + 1);

          if (str1.length() > maxStr.length() && str1.length() >= str2.length()) {
            maxStr = str1;
          }
          if (str2.length() > maxStr.length() && str1.length() < str2.length()) {
            maxStr = str2;
          }
        }
        return maxStr;
    }
    
  public String checkPalind(String s, int left, int right) {
    while (left >= 0 && right < s.length()) {
      if (s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
      } else {
        break;
      }
    }
    left++; //while문에서 감소 시키고 끝났으므로, 원래 위치로 돌아오기 위해 다시 돌려줌.
    right--; //while문에서 증가 시키고 끝났으므로, 원래 위치로 돌아오기 위해 다시 돌려줌.
    return s.substring(left, right + 1);
  }

}

 

로직 설명.

1.일단 문자열이 회문이려면 짝수 or 홀수여야 함.

2.짝수인 경우와, 홀수인 경우를 나눠서 계산함.

3. for loop로 문자열의 첫번째부터 검색해들어감

4. 0번 인덱스 부터시작하여 

  while문으로 해당 인덱스부터 좌, 우로 뻗어나가면서 문자열이 일치하는지 검색한다.

 

ex) "aba"

for loop

-> a 부터 시작 

(홀수)a 와 바로 옆문자까지 포함한 (짝수)ab에 대해서 확인을 진행

홀수 케이스 . a의 경우 우측에는 문자열이 있지만, 좌측에는 문자열이 없으므로 회문이 아님 다음으로 넘어감

짝수 케이스 . ab의 경우 a, b가 서로 다른 문자이므로 회문이 아님 다음으로 넘어감

 

이제 다음 for문 다음 인덱스로 접근

-> b부터 시작

(홀수) b와 바로 옆문자까지 포함한 (짝수)ba에 대해서 확인을 진행

홀수 케이스 . b의 경우 좌측, 우측에 모두 문자열이 있으므로 해당 문자열을 비교, 같으므로 회문 문자열이라 판단.

                     좌우로 한칸씩 뻗어감.

                     aba에 대해 다시 우측과 좌측 문자열 확인, 좌우측 더이상 문자열이 없으므로 다음으로 넘어감. 

                     "aba"를 리턴함.

짝수 케이스 . ab의 경우 a, b가 서로 다른 문자이므로 회문이 아님 다음으로 넘어감

 

이제 maxStr의 length보다 리턴받은 "aba"가 더 크므로 maxStr에 "aba"를 저장함.

 

이제 다음 for문 인덱스로 접근

-> a부터 시작

위와 동일한 로직을 수행하며, 좌측으로 뻗어갈수 있지만 오른쪽으로는 불가하므로 더이상 "aba"보다 큰 회문 문자열 생성불가

 

최종적으로 "aba"가 리턴됨.