[LeetCode#131] Palindrome Partitioning

 

❐ Description

---

이번 문제도 [LeetCode#93] Restore IP Addresses와 마찬가지로  문자열을 동적으로

분할하는 로직이 추가적으로 필요하다.

 

 

 

 

 

❐ 풀이 전략

---

☑️ 주어진 문자열의 분할 시작점을 cursor 변수에 저장한다.

☑️ cursor를 시작으로 하는 for문 input의 길이만큼 순회한다. (int i = cursor;)

☑️ 부분 문자열의 Palindrome 여부를 확인한다.

☑️ 시작 : cursor, 종료 : i + 1

 

 

 

 

 

❐ Solution

---

public class Solution {

    private final List<List<String>> subsets = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backTracking(s, 0, new ArrayList<>());
        return subsets;
    }

    private void backTracking(
            String input,
            int cursor,
            List<String> subset
    ) {
        if (input.length() == cursor) {
            subsets.add(new ArrayList<>(subset));
            return;
        }

        for (int i = cursor; i < input.length(); i++) {
            if (isPalindrome(input, cursor, i)) {
                String substring = input.substring(cursor, i + 1);
                subset.add(substring);
                backTracking(input, i + 1, subset);
                subset.removeLast();
            }
        }
    }

    private boolean isPalindrome(String input, int start, int end) {
        while (start <= end) {
            char startChar = input.charAt(start);
            char endChar = input.charAt(end);
            start++;
            end--;
            if (startChar != endChar) {
                return false;
            }
        }
        return true;
    }
}