Here is my answer


  • 0
    S

    import java.util.*;

    class Solution {
    private boolean isPalindrome(String s) {
    s = s.replaceAll("[^a-zA-Z0-9]","").toLowerCase();
    int i = 0; int j = s.length() - 1;
    if (j <= 0) return true;

        while (true) {
            if (i >= j) break;    
            if (s.charAt(i++) != s.charAt(j--))
                return false;
        }
        
        return true;
    }
    
    public List<List<String>> partition(String s) {
        Map<Integer, List<List<String>>> results = new HashMap<Integer, List<List<String>>>();
        
        for (int from = s.length(); from >= 0; from--) {
            int subLength = s.length() - from;
            
            List<List<String>> result = new ArrayList<List<String>>();
            if (subLength == 0) {
                List<String> l = new ArrayList<String>();
                result.add(l);
            }
            
            for (int i = from + 1; i <= s.length(); i++) {
                String pal = s.substring(from, i);
                if (isPalindrome(pal)) {
                    List<List<String>> listPalins = results.get(i);
                    for (List<String> palins: listPalins) {
                    	List<String> newPalins = new ArrayList<String>();
                    	newPalins.add(pal);
                    	for (String subPal: palins) {
                    		newPalins.add(subPal);
                    	}
                        result.add(newPalins);
                    }
                }
            }
            results.put(from, result);
        }
        return results.get(0);
    }
    

    }

    I used the DP:
    partition(s)
    for each sub=substring(0, i) of s
    if sub is palindrome
    insert sub to partition(substring (i, s.length()) of s)

    Thank you!


  • 0
    S

    Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.


Log in to reply
 

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