[LeetCode] 647. Palindromic Substrings - Java

https://leetcode.com/problems/palindromic-substrings/

Palindromic Substrings - LeetCode

---

문제

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

 

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

 

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

---

풀이

풀이 과정

전체적인 풀이 과정은 LeetCode 5.Longest Palindromic Substring와 거의 같다.

https://hyojun.tistory.com/entry/LeetCode-5-Longest-Palindromic-Substring-Java

[LeetCode] 5. Longest Palindromic Substring - Java

 

주어진 문자열 s의 모든 문자에 대해서 탐색하며 각각 홀수 길이인 경우, 짝수 길이인 경우의 Palindrome이 몇 개인지 누적시켜 최종 return 한다.

public int countSubstrings(String s) {
    int answer = 0;

    // s의 모든 문자에 대해서 탐색
    for(int i = 0; i < s.length(); i++) {
        // 홀수 길이인 Palindrome 개수
        answer += countPalindrome(s, i, i);
        // 짝수 길이인 Palindrome 개수
        answer += countPalindrome(s, i, i + 1);
    }

    return answer;
}

 

각 문자에 대해서 Palindrome이 몇 개인지 카운트하는 함수는 다음과 같다.
탐색 대상 문자열 s와 왼쪽, 오른쪽 인덱스 left, right를 전달 받아 왼쪽 인덱스와 오른쪽 인덱스가 문자열 s의 끝에 도달할 때 까지 반복한다.
만약 양쪽의 글자가 같은 경우 카운트를 증가시키고 인덱스를 한 칸씩 이동한다.
양쪽의 글자가 다른 경우에는 더 이상 Palindrome이 될 수 없으므로 탐색을 종료한다.
탐색이 종료된 후 카운트를 최종 return한다.

/**
 * @param s         탐색할 문자열
 * @param left      탐색을 시작할 왼쪽 인덱스
 * @param right     탐색을 시작할 오른쪽 인덱스
 * @return
 */
public int countPalindrome(String s, int left, int right) {
    int count = 0;

    // 왼쪽 인덱스와 오른쪽 인덱스가 끝에 도달할 때 까지 반복
    while(left >= 0 && right < s.length()) {
        // 양쪽의 글자가 같은 경우 카운트를 증가시키고 인덱스를 한칸씩 이동
        if(s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        } 
        // 양쪽의 글자가 다른 경우 탐색 종료
        else {
            break;
        }
    }

    return count;
}

---

최종 코드

class Solution {
    public int countSubstrings(String s) {
        int answer = 0;
        
        // s의 모든 문자에 대해서 탐색
        for(int i = 0; i < s.length(); i++) {
            // 홀수 길이인 Palindrome 개수
            answer += countPalindrome(s, i, i);
            // 짝수 길이인 Palindrome 개수
            answer += countPalindrome(s, i, i + 1);
        }

        return answer;
    }

    /**
     * @param s         탐색할 문자열
     * @param left      탐색을 시작할 왼쪽 인덱스
     * @param right     탐색을 시작할 오른쪽 인덱스
     * @return
     */
    public int countPalindrome(String s, int left, int right) {
        int count = 0;
        
        // 왼쪽 인덱스와 오른쪽 인덱스가 끝에 도달할 때 까지 반복
        while(left >= 0 && right < s.length()) {
            // 양쪽의 글자가 같은 경우 카운트를 증가시키고 인덱스를 한칸씩 이동
            if(s.charAt(left) == s.charAt(right)) {
                count++;
                left--;
                right++;
            } 
            // 양쪽의 글자가 다른 경우 탐색 종료
            else {
                break;
            }
        }
        
        return count;
    }
}

---