Print all palindromes in Palindrome Partitioning

shriyanshi24jindal

Mar 30th, 2026

116

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 8.77 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/**
[]
/ \
"a" "aa"
/ \
"a" "b"
| |
"b" END
|
END
*/
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
List<String> current = new ArrayList<>();
solve(s, 0, s.length(), result, current);
return result;
}
public void solve(String s, int i, int j, List<List<String>> result, List<String> current)
{
// base condition
if(i == s.length()) {
result.add(new ArrayList<>(current));
return;
}
// Define k-loop scheme
for(int k=i; k<=j-1; k++)
{
if(isPalindrome(s, i, k))
{
// choose
current.add(s.substring(i, k+1));
// explore
solve(s, k+1, j, result, current);
// un-choose (backtrack)
current.remove(current.size() - 1);
}
}
return;
}
public boolean isPalindrome(String s, int i, int j)
{
String s1 = s.substring(i, j+1);
String s2 = new StringBuilder(s1).reverse().toString();
return s1.equals(s2);
}
}

RAW Paste Data Copied

class Solution {
    /**
            []
           /   \
        "a"     "aa"
       /          \
    "a"            "b"
     |              |
    "b"             END
     |
    END
    */
    
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> current = new ArrayList<>();

solve(s, 0, s.length(), result, current);
        return result;
    }

public void solve(String s, int i, int j, List<List<String>> result, List<String> current)
    {
        // base condition
        if(i == s.length()) {
            result.add(new ArrayList<>(current));
            return;
        }
        // Define k-loop scheme
        for(int k=i; k<=j-1; k++)
        {
            if(isPalindrome(s, i, k))
            {
                // choose
                current.add(s.substring(i, k+1));

// explore
                solve(s, k+1, j, result, current);

// un-choose (backtrack)
                current.remove(current.size() - 1);
            }
        }
        return;
    }

public boolean isPalindrome(String s, int i, int j)
    {
        String s1 = s.substring(i, j+1);
        String s2 = new StringBuilder(s1).reverse().toString();
        
        return s1.equals(s2);
    }
}