[알고리즘] #Palindromic Substrings

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

Loading...

문제

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

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.

 

번역

문자열이 주어졌을 때, 앞으로 읽어도, 뒤에서 읽어도 내용이 같은 문자열의 갯수를 구하세요.

문자열이 같더라도, 시작 index와 마지막 index가 다르면 갯수에 포함시킵니다.

(palindromic substrings : 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 문자열)

 

 

---

#이중 for문을 이용한 풀이

주어진 문자열을 Character 배열로 변환한 뒤, 한 글자씩 이어 붙이면서 해당 문자열이 palindromic string인지 확인한다.

먼저, 한 글자인 경우에는 무조건 palindromic string 이므로 count를 추가한다.

해당 문자열이 palindromic string 인지 확인하는 방법은 StrinngBuffer를 이용해서 확인했다. 

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        System.out.println(">>> str : abc  ====> answer : " + solution.countSubstrings("abc"));
        System.out.println(">>> str : aaa  ====> answer : " + solution.countSubstrings("aaa"));

    }
}

class Solution {
    public int countSubstrings(String s) {
        if(s == null || s.equals("")) {
            return 0;
        }

        char[] charArr = s.toCharArray();
        int cnt = 0;

        for(int i=0; i<charArr.length; i++) {
            String pStr = Character.toString(charArr[i]);
            System.out.println(">>> str : abc  ====> answer: " + pStr);
            cnt++;
            for(int j=i+1; j<charArr.length; j++) {
                pStr = pStr.concat(Character.toString(charArr[j]));
                // palindromic string인지 확인
                if(pStr.equals(new StringBuffer(pStr).reverse().toString())) {
                    cnt++;
                    System.out.println(">>> str : abc  ====> answer: " + pStr);
                }
            }
        }

        return cnt;
    }
}

결과 값

>>> str : abc  ====> answer: a
>>> str : abc  ====> answer: b
>>> str : abc  ====> answer: c
>>> str : abc  ====> answer : 3
>>> str : abc  ====> answer: a
>>> str : abc  ====> answer: aa
>>> str : abc  ====> answer: aaa
>>> str : abc  ====> answer: a
>>> str : abc  ====> answer: aa
>>> str : abc  ====> answer: a
>>> str : aaa  ====> answer : 6