[99클럽 코테 스터디 22일차 TIL] 문자열

qk·2024년 6월 19일
0

회고

목록 보기
22/33
post-thumbnail
post-custom-banner

📖 오늘의 학습 키워드
문자열

오늘의 회고

문제

[Longest Palindromic Substring]
https://leetcode.com/problems/longest-palindromic-substring/description/

나의 해결

class Solution {
    public String answer;
    public String longestPalindrome(String s) {
        answer = s.substring(0, 1);
        for(int i = 1; i < s.length(); i++) {
            find(i-1, i, s);
            find(i-1, i+1, s);
        }
        return answer;
    }
    public void find(int l, int r, String s) {
        String str = "";
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            str = s.substring(l, r+1);
            l--;
            r++;
        }
        if(answer.length() < str.length()) {
            answer = str;
        }
    }
}
  1. 회문의 최소 길이는 문자가 하나일 때인 1이기 때문에 answer는 s의 첫 번째 문자로 초기화한다.
  2. for 문으로 문자열 s의 두 번째 문자부터 마지막 문자까지 돌며 각 문자를 기준으로 최대 길이의 회문을 찾는다.
  3. 회문이 만들어지는 경우는 두 가지이다.
    회문을 찾는 방법은 같으나 l(왼쪽 인덱스)과 r(오른쪽 인덱스)의 초깃값이 다르다.
    1) 짝수 길이의 회문
    l: i-1
    r: i
    2) 홀수 길이의 회문
    l: i-1
    r: i+1
  4. 각 경우마다 만들어지는 최대 길이 회문을 찾는다. (find 함수)
    1. l이 0보다 크거나 같고 r이 s의 길이보다 작으며, l과 r의 위치에 있는 문자가 같을 때까지 while 문을 돌며 l의 값을 하나씩 줄이고 r의 값을 하나씩 늘린다. 그리고 생성되는 회문을 str에 저장한다.
    2. str의 길이가 answer의 길이보다 길면 str의 값으로 answer를 갱신한다.
post-custom-banner

0개의 댓글