DP Java Solution


  • 0
    X

    The idea is if the string starts from 0 is palindrome, Add to stack, and try the same thing to the rest of that string. If all string in the stack are palindromes, add all of them into result.

    public class Solution {
        private boolean isPalindrome(String s, int start, int end) {
            while(start < end) {
                if(s.charAt(start) != s.charAt(end)) return false;
                start++;
                end--;
            }
            return true;
        }
        private void dfs(String s, int start, int end, Stack<String> intermResult, List<List<String>> result) {
            if(start == end) {
                result.add(new ArrayList<String>(intermResult));
                return;
            }
            for(int i=0; i<s.length(); i++) {
                if(isPalindrome(s, 0, i)) {
                    intermResult.push(s.substring(0,i+1));
                    dfs(s.substring(i+1), i+1, s.length(), intermResult, result);
                    intermResult.pop();
                }
            }
        }
        public List<List<String>> partition(String s) {
            List<List<String>> result = new ArrayList<List<String>>();
            Stack<String> interimResult = new Stack<String>();
            dfs(s, 0, s.length(), interimResult, result);
            return result;
        }
    }

Log in to reply
 

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