Problem Explanation

The problem can be understood as follows:

Given a string s, the task is to partition the string such that every substring after partitioning is a palindrome. A palindrome is a word, phrase, number, or other sequences of characters that reads the same backward or forward. To optimize the solution, we can use the technique of Depth-First Search (DFS).

For example,

1
2
3Input: "aab"
4Output: [ ["aa","b"], ["a","a","b"] ]
5
6Explanation:
7In this example, the string 'aab' can be partitioned into ["aa","b"] and ["a","a","b"] where all substrings in the partition are palindromes.

Solution Approach

The main idea to solve this problem is using the DFS algorithm to check every possible partition of the given string. Firstly, we run an outer loop through the given string. For every mid-point found in the outer loop, we check if the string from the start index to the current mid-point is a palindrome. If the string is indeed a palindrome, then we add the substring to the result list and recursively proceed to solve the rest of the problem starting from index r+1 (r refers to the end index of the substring). If the string is not a palindrome, we just ignore this and proceed to the next substring.

Solution

Python Solution

Here is the Python implementation of the above-explained approach:

1
2python
3class Solution:
4    def partition(self, s: str) -> List[List[str]]:
5        def dfs(i, path):
6            if i == len(s):
7                result.append(path)
8                return
9            for r in range(i,len(s)):
10                if s[i:r + 1] == s[i:r + 1][::-1]:
11                    dfs(r + 1, path + [s[i:r + 1]])
12
13        result = []
14        dfs(0, [])
15        return result

Java Solution

1
2java
3class Solution {
4    public List<List<String>> partition(String s) {
5        List<List<String>> result = new ArrayList<List<String>>();
6        dfs(s, 0, new ArrayList<String>(), result);
7        return result;
8    }
9    
10    void dfs(String s, int start, List<String> currentList, List<List<String>> result) {
11        if(start==s.length()) {
12            result.add(new ArrayList<>(currentList));
13            return;
14        }
15        for(int end=start; end<s.length(); end++) {
16            if(isPalindrome(s, start, end)) {
17                currentList.add(s.substring(start, end + 1));
18                dfs(s, end + 1, currentList, result);
19                currentList.remove(currentList.size() - 1);  // remove for backtracking 
20            }
21        }
22    }
23
24    boolean isPalindrome(String s, int low, int high) {
25        while(low<high) {
26            if(s.charAt(low++)!=s.charAt(high--)) {
27                return false;
28            }
29        }
30        return true;
31    }
32}

JavaScript Solution

1
2javascript
3var partition = function(s) {
4    var res = [];
5    dfs(0, []);
6    return res;
7
8    function dfs(start, path) {
9        if (start === s.length) {
10            res.push(path);
11            return;
12        }
13        for (var i = start; i < s.length; i++) {
14            var sub = s.substring(start, i + 1);
15            if (!isPal(sub)) continue; // backtracking
16            dfs(i + 1, path.concat([sub]));
17        }
18    }
19
20    function isPal(s) {
21        var len = s.length;
22        for (var i = 0; i < len / 2; i++) {
23            if (s.charAt(i) !== s.charAt(len - i - 1)) return false;
24        }
25        return true;
26    }
27};

C++ Solution

1
2c++
3class Solution {
4public:
5    vector<vector<string>> partition(string s) {
6        vector<vector<string>> ans;
7        dfs(s, 0, {}, ans);
8        return ans;
9    }
10    
11private:
12    void dfs(const string& s, int start, vector<string> path, vector<vector<string>>& ans) {
13        if (start == s.size()) {
14            ans.push_back(path);
15            return;
16        }
17        for (int i = start; i < s.size(); ++i)
18            if (isPalindrome(s, start, i)) {
19                path.push_back(s.substr(start, i - start + 1));
20                dfs(s, i + 1, path, ans);
21                path.pop_back();
22            }
23    }
24
25    bool isPalindrome(const string& s, int l, int r) {
26        while (l < r),
27          if (s[l++] != s[r--])
28            return false;
29        return true;
30    }
31};

C# Solution

1
2C#
3public class Solution {
4    public IList<IList<string>> Partition(string s) {
5        IList<IList<string>> result = new List<IList<string>>();
6        Dfs(s, 0, new List<string>(), result);
7        return result;
8    }
9    
10    void Dfs(string s, int start, List<string> currentList, IList<IList<string>> result) {
11        if (start == s.Length) {
12            result.Add(new List<string>(currentList));
13            return;
14        }
15        for(int end = start; end < s.Length; end++) {
16			if (IsPalindrome(s, start, end)) {
17				currentList.Add(s.Substring(start, end - start + 1));
18				Dfs(s, end + 1, currentList, result);
19				currentList.RemoveAt(currentList.Count - 1);  
20			}
21		}
22    }
23
24    bool IsPalindrome(string s, int low, int high) {
25        while (low < high) {
26			if (s[low++] != s[high--])
27				return false;
28		}
29		return true;
30    }
31}

In the solution, we make use of DFS to explore all possible partitions of the given string. This is done by recursively dividing the string into two halves and check if the left half String is a palindrome. If it is, recursively perform the check on the right half, and so forth until we reach the end of the string. With DFS we use backtracking, i.e., when one path ends we go back to the node, where we left off and go along the next path. Thus this approach falls under the categories of backtracking algorithms.# Time Complexity Analysis

The time complexity for all the solutions is O(N * 2^N), where N is the length of the string. This is because, in the worst-case scenario where every character in the input string is the same, we have to iterate through every substring's partition.

For example, with the string "aaa...aaa", we have "a", "a", "a", ..., "a", "aa", "aa", ..., "aaa", "aaa", ..., "aaaa", ... , "aaaa..." and so forth. In other words, we have roughly 2^N different ways to partition the string, and for each partition, we spend O(N) time to convert it into a list and output it.

The time complexity of checking a string for being a palindrome is O(N), the time complexity of slicing a string is also O(N). Hence, the overall time complexity becomes O(N*(2^N)).

Space Complexity Analysis

The space complexity for all the solutions is O(N). The major space cost comes from the recursive call stack as well as the currentList we used to keep the current partition. In the worst case, where the input string is a palindrome itself, the maximum depth of the recursion is N (the length of the string), so the maximum length of the currentList is also N, and thus the space complexity is O(N).

Conclusion

In conclusion, given a string, we can partition it into all the possible palindromic substrings using the depth-first search algorithm. Combine it with backtracking techniques, we can efficiently solve this problem by exploring all the possible partitions and retrieving the valid ones. The provided solutions in Python, Java, JavaScript, C++, and C# show how we can implement these concepts programmatically.