131. Palindrome Partitioning LeetCode Solution

In this guide, you will get 131. Palindrome Partitioning LeetCode Solution with the best time and space complexity. The solution to Palindrome Partitioning problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Palindrome Partitioning solution in C++
Palindrome Partitioning solution in Java
Palindrome Partitioning solution in Python
Additional Resources

131. Palindrome Partitioning LeetCode Solution image

Problem Statement of Palindrome Partitioning

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

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.

Complexity Analysis

Time Complexity: O(n \cdot 2^n)
Space Complexity: O(n \cdot 2^n)

131. Palindrome Partitioning LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

131. Palindrome Partitioning LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

131. Palindrome Partitioning LeetCode Solution in Python

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
 # code by PROGIEZ