recursion with memorization java solution, easy to understand


  • 1
    F

    This problem is very similar to Word Break 2.
    For example, a string of length n can be partitioned into n pairs:

    • "" + s1s2...sn
    • s1 + s2...sn
    • s1s2 + s3...sn
    • s1s2...s(n-1) + sn

    The first part we call it a word, the second part we call it a sentence. Firtly, we check if the word is a palindrome, if true, we do recursion on the sentence. To reduce redundant computation, we use a HashMap to store intermediate results, and here is the AC java code:

    private Map<String, List<List<String>>> map = new HashMap<>();
    
        public boolean isPalindrome(String s) {
            int i = 0, j = s.length() - 1;
            while (i < j) {
                if (s.charAt(i++) != s.charAt(j--)) {
                    return false;
                }
            }
            return true;
        }
    
        public List<List<String>> partition(String s) {
            if (map.containsKey(s)) {
                return map.get(s);
            }
            List<List<String>> lists = new ArrayList<>();
            if (isPalindrome(s)) {
                lists.add(new ArrayList<>(Arrays.asList(s)));
            }
            int n = s.length();
            for (int i = 1; i < n; i++) {
                String word = s.substring(0, i);
                if (isPalindrome(word)) {
                    List<List<String>> right = partition(s.substring(i));
                    for (List<String> list : right) {
                        List<String> list1 = new ArrayList<>();
                        list1.add(word);
                        list1.addAll(list);
                        lists.add(list1);
                    }
                }
            }
            map.put(s, lists);
            return lists;
        }
    

Log in to reply
 

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