# Iterative solution using table (Java)

• ``````/**
* create a table of size s.length() + 1, all initialize to null except first one.
* each cell contains a list of paths that can reach this cell;
* if a cell is not null (reachable), we try to move to next cell by finding palindromes
* in the substring.
* in the end, the last cell should contain results.
* the table takes care of DP/ memoization.
*/
``````

Code:

``````public List<List<String>> partition(String s) {
List<List<List<String>>> table = new ArrayList<List<List<String>>>(s.length() + 1);
List<List<String>> lists0 = new ArrayList<List<String>>();
for (int i = 1; i <= s.length(); i++)
for (int i = 0; i <= s.length(); i++) {
List<List<String>> lists = table.get(i);
if (lists != null) {
for (int end = i + 1; end <= s.length(); end++) {
String next = s.substring(i, end);
if (isPalindrome(next)) {
List<List<String>> nextLists = table.get(end);
if (nextLists == null) {
nextLists = new ArrayList<List<String>>();
table.set(end, nextLists);
}
for (List<String> list : lists) {
List<String> nextList = new ArrayList<String>(list);
}
}
}
}
}

return table.get(s.length());
}

private boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right))
return false;
left++;
right--;
}
return true;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.