131. Palindrome Partitioning
https://leetcode.com/problems/palindrome-partitioning/
문제
풀이
예를 들어 s = "aabaa"라고 생각해보자.
left, right로 파티션을 나눈다.
1. i = 0일 때 left = "a" right = "abaa"이다. left는 팔린드롬이니 right를 또 left, right로 나누어 파티션을 만들고 팔린드롬인지 확인한다.
2. right = "abaa"에서 left = "a, right = "baa"로 나눈다. left는 팔린드롬이니 right를 또 left, right로 나누어 파티션을 만들고 팔린드롬인지 확인한다.
3. right = "baa"에서 left = "b", right = "aa"로 나눈다. left는 팔린드롬이고 right를 left, right로 나누어 파티션을 만들고 팔린드롬인지 확인한다.
4. right = "aa"에서 left = "a", right = "a"로 나눈다. left, right 둘 다 팔린드롬이므로 ["a", "a"]을 리턴한다.
5. right = "aa"에서 left = "aa", right = ""로 나눈다. ["aa"]를 리턴한다. 이제 백트래킹을 시작한다.
6. right = "baa"에서 left= "b", right = "aa"에서 right는 [["a", "a"], ["aa"]]로 리턴되었으므로 left와 right가 합쳐진 [["b", "a", "a"], ["b", "aa"]]를 리턴한다.
7. right = "abaa"에서 left = "a", right = "baa"일 때 right 값은 리턴되었으므로 left와 right가 합쳐진 [["a", "b", "a", "a"], ["a", "b", "aa"]]가 될 것이다. 하지만 left = "a"뿐만 아니라 "aba"도 팔린드롬이므로 이와 같이 진행하여 리턴된 값을 받아온다. [["aba", "a"]]를 받아오고 합쳐지면 [["a", "b", "a", "a"], ["a", "b", "aa"], ["aba", "a"]]를 리턴한다.
8. 백트래킹하여 left = "a", right = "abaa"일 때 right값은 리턴받았으므로 [["a", "a", "b", "a", "a"], ["a", "a", "b", "aa"], ["a", "aba", "a"]]가 될 것이다.
9. 하지만 left = "a"말고도 "aa", "aabaa"가 있다. 이와 같은 방법으로 한다면 최종
[["a","a","b","a","a"],["a","a","b","aa"],["a","aba","a"],["aa","b","a","a"],["aa","b","aa"],["aabaa"]]가 리턴될 것이다.
결과
느낀점
- a = ["a", "b"] b=["aa", "bb"] 에서
a.extend(b) => ["a", "b", "aa", "bb"]가 된다.
