# Palindrome Partitioning Leetcode Solution

In this post, we are going to solve the Palindrome Partitioning Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

## Problem

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

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.

Now, lets see the leetcode solution of Palindrome Partitioning Leetcode Solution.

### 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```

### Palindrome Partitioning Leetcode Solutionin CPP

```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, 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;
}
};```

### 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()) {
return;
}

for (int i = start; i < s.length(); ++i)
if (isPalindrome(s, start, i)) {
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;
}
}```

Note: This problem Palindrome Partitioning is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purpose.

Sharing Is Caring