[leetcode 647] Palindromic Substrings

palindromic substring을 세는 문제

 

Example 1:

Input: "abc" Output: 3

Explanation: Three palindromic strings: "a", "b", "c".

 

Example 2:

Input: "aaa" Output: 6

Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

 

Note:

1. The input string length won't exceed 1000.

다행히 문자열이 1000을 안넘어서 그런지 for문 돌려도 통과했다...하지만 몹시 느린 것이 사실

class Solution {
public:
    int countSubstrings(string s) {
        int result = 0;
        if(s.length() == 0){
            return result;
        }
        result += s.length();
        
        for(int i=0;i<s.length();i++){
            //i is the length of substring
            for(int j=i+1; j<s.length(); j++){
                int start = i;
                int end = j;
                bool flag = true;
                
                if(s[start] == s[end]){
                    while(start<end){
                        
                        if(s[start]!=s[end]){
                            flag = false;
                            break;
                        }
                        start++;
                        end--;
                    }
                    
                    if(flag == true){
                        cout<<i<<" "<<j<<"\n";
                        result++;
                    }
                }
            }
        }
        return result;
    }
};

 

좀 더 빠른 방법을 알아보자 - 다른 사람 풀이 참고

위에서 쓴 방법은 string의 각 idx i에 j만큼의 길이인 palindromic substring이 존재하는지 체크하는 구조이다.

i                                             j

  i+1 i +2  ....

                       .....     j-2  j-1

 

 

방법을 바꿔서 가운데 만나는 지점을 시작점으로 해보자

서브스트링의 길이가 홀수인 경우 i에서 출발한다.

짝수인 경우 i와 i+1에서 출발한다. 두 지점중 하나라도 조건을 벗어난다면 while문을 빠져나온다.

class Solution {
public:
    int countSubstrings(string s) {
        int L = s.length();
        
        int res = 0;
        for(int i=0; i<L; i++){
            int j=i, k=i;
            while(j>=0 && k<L && s[j] == s[k]){
                res++;
                j--;
                k++;
            }
            
            j=i; k=i+1;
            while(j>=0 && k<L && s[j] == s[k]){
                res++;
                j--;
                k++;
            }
        }
        
        return res;
    }
};

 

 

사실 이 문제는 dp로 표기되어 있다. dp로 푼 풀이도 살펴보자.

dp를 이차원 배열로 선언: dp[i][j]는 index가 i부터 j까지 인 서브스트링이 palindromic한지 true/false를 저장한다.서브스트링의 길이가 1인 경우, 즉 i=j인 경우 모두 true이다.

 

서브스트링의 길이가 3이상인 경우i가 start idx, j가 end idx라고 두고if (dp[i+1][j-1] = true && s[i] == s[j]) then dp[i][j] = true 의 식을 도출할 수 있다.

 

int countSubstrings(String s) {
    if (s.length() == 0) {
        return 0;
    }
    
    int n = s.length();
    // dp[i][j] will be false if substring str[i..j]
    // is not palindrome. Else, dp[i][j] will be true
    bool dp[n][n];

    int count = 0;

    // 길이가 1인 경우 전부 palindrome
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        count++;
    }

    int i, ls, j;

    //substring 길이가 2일 때
    for (i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            count++;
        }
    }

    // Check for lengths greater than 2
    // ls는 substring 길이
    for (ls = 3; ls <= n; ls++) {
        // i is the starting index
        for (i = 0; i < n - ls + 1; i++) {
            // j is ending index of substring from starting index i and length ls
            j = i + ls - 1;
           
            if (dp[i + 1][j - 1] && s[i] == s[j]) {
                dp[i][j] = true;
                count++;
            }
        }
    }

    return count;
}