Skip to content

131. Palindrome Partitioning 👍

  • Time: $O(n \cdot 2^n)$
  • Space: $O(n \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  vector<vector<string>> partition(string s) {
    vector<vector<string>> ans;
    dfs(s, 0, {}, ans);
    return ans;
  }

 private:
  void dfs(const string& s, int start, vector<string>&& path,
           vector<vector<string>>& ans) {
    if (start == s.length()) {
      ans.push_back(path);
      return;
    }

    for (int i = start; i < s.length(); ++i)
      if (isPalindrome(s, start, i)) {
        path.push_back(s.substr(start, i - start + 1));
        dfs(s, i + 1, std::move(path), ans);
        path.pop_back();
      }
  }

  bool isPalindrome(const string& s, int l, int r) {
    while (l < r)
      if (s[l++] != s[r--])
        return false;
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public List<List<String>> partition(String s) {
    List<List<String>> ans = new ArrayList<>();
    dfs(s, 0, new ArrayList<>(), ans);
    return ans;
  }

  private void dfs(final String s, int start, List<String> path, List<List<String>> ans) {
    if (start == s.length()) {
      ans.add(new ArrayList<>(path));
      return;
    }

    for (int i = start; i < s.length(); ++i)
      if (isPalindrome(s, start, i)) {
        path.add(s.substring(start, i + 1));
        dfs(s, i + 1, path, ans);
        path.remove(path.size() - 1);
      }
  }

  private boolean isPalindrome(final String s, int l, int r) {
    while (l < r)
      if (s.charAt(l++) != s.charAt(r--))
        return false;
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def partition(self, s: str) -> list[list[str]]:
    ans = []

    def isPalindrome(s: str) -> bool:
      return s == s[::-1]

    def dfs(s: str, j: int, path: list[str], ans: list[list[str]]) -> None:
      if j == len(s):
        ans.append(path)
        return

      for i in range(j, len(s)):
        if isPalindrome(s[j: i + 1]):
          dfs(s, i + 1, path + [s[j: i + 1]], ans)

    dfs(s, 0, [], ans)
    return ans