[LeetCode] 131. Palindrome Partitioning

Problem

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

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

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

• 1 <= s.length <= 16
• s contains only lowercase English letters.

---

Solution

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> list = new ArrayList<List<String>>();
        makeList(s, list, new ArrayList<String>());
        return list;
    }
    private void makeList(String s, List<List<String>> list, List<String> tmpList) {
        // stop recursion
        if (s.length() == 0) {
            list.add(new ArrayList(tmpList));
            return;
        }
        for (int i = 1; i <= s.length(); i++) {
            String subStr = s.substring(0, i);
            if (isPalindrome(subStr)) {
                tmpList.add(subStr);
                String remainder = s.substring(i, s.length());
                makeList(remainder, list, tmpList);
                tmpList.remove(tmpList.size() - 1);
            }
        }
        return ;
    }
    private boolean isPalindrome(String s) {
        for (int i = 0; i < s.length() / 2; i++)
            if (s.charAt(i) != s.charAt(s.length() - i - 1))
                return false;
        return true;
    }
}

Explanation

• 아래와 같이, 문제의 반환값을 보면 큰 리스트에 작은 리스트가 들어있는 것을 볼 수 있다. 이는 반복을 통해 작은 리스트를 만들고 큰 리스트에 추가하는 반복이 필요하다는 의미이다.

  Input: s = "aab"
  Output: [["a","a","b"],["aa","b"]]
  

• 먼저 문자열이 Palindrome인지 확인하는 메서드를 선언해 코드를 간결하게 작성할 수 있도록 한다.

  private boolean isPalindrome(String s) {
    for (int i = 0; i < s.length() / 2; i++)
        if (s.charAt(i) != s.charAt(s.length() - i - 1))
            return false;
    return true;
  }
  

• 큰 리스트를 만들려면 먼저 작은 리스트를 만들어야 한다. 작은 리스트를 만들기 위해 문자열을 substring으로 만들고 Palindrome인지 확인하고 tmpList에 추가하는 for반복문을 선언한다.

  for (int i = 1; i <= s.length(); i++) {
    String subStr = s.substring(0, i);
    if (isPalindrome(subStr))
        tmpList.add(subStr);
  }
  

• 위의 for반복문에서 증감시킬 수 있는 변수가 i하나 뿐이라 tmpList에 겹치는 문자열이 들어가게 된다. 그리고 tmpList에 들어간 문자열을 제외한 나머지 문자열을 가지고 for반복문을 수행해야 한다.
• 이를 해결하기 위해 for반복문을 함수에 포함시키고 이를 재귀 함수로 반복 호출하도록 한다.
• 재귀 함수가 반복될 때, tmpList의 마지막 요소가 제거되도록 해야 올바른 tmpList가 만들어지므로 재귀 함수가 종료된 후에 tmpList의 마지막 요소를 제거하도록 한다.

  private void makeList(String s, List<List<String>> list, List<String> tmpList) {
    for (int i = 1; i <= s.length(); i++) {
        String subStr = s.substring(0, i);
        if (isPalindrome(subStr)) {
            tmpList.add(subStr);
            // remainder after adding in tmpList
            String remainder = s.substring(i, s.length());
            makeList(remainder, list, tmpList);
            tmpList.remove(tmpList.size() - 1);
        }
    }
    return ;
  }
  

• 재귀 함수의 호출이 종료되는 시점이 필요하다. 파라미터로 전달받은 문자열이 없을 때, 재귀 함수의 호출이 종료되어야 하고, tmpList가 list에 추가되어야 하므로, 이를 고려해 if조건문을 작성한다.

  private void makeList(String s, List<List<String>> list, List<String> tmpList) {
    // stop recursion
    if (s.length() == 0) {
        list.add(new ArrayList(tmpList));
        return;
    }
    for (int i = 1; i <= s.length(); i++) {
        String subStr = s.substring(0, i);
        if (isPalindrome(subStr)) {
            tmpList.add(subStr);
            String remainder = s.substring(i, s.length());
            makeList(remainder, list, tmpList);
            tmpList.remove(tmpList.size() - 1);
        }
    }
    return ;
  }
  

• 반환용 list를 선언하고 재귀 함수의 파라미터로 전달한다. tmpList는 재귀 함수내에서만 사용되므로 새로운 tmpList를 파라미터로 전달한다. 그리고 만들어진 리스트를 반환한다.

  List<List<String>> list = new ArrayList<List<String>>();
  makeList(s, list, new ArrayList<String>());
  return list;