Leetcoder - Binary Tree Maximum Path Sum

 Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int max = root.val;
     
        return getSum(root, max)[0];
    }
 
    public int[] getSum(TreeNode node, int max) {
        int[] vals = new int[2];
        vals[0] = max;
        vals[1] = node.val;
        int leftSum = 0;
        int rightSum = 0;
        int sum = node.val;
        if(node.left!=null) {
            int[] leftV = getSum(node.left, max);
            leftSum = leftV[1] + node.val;
            if(leftV[0]>max) {
                max = leftV[0];
            }
            if(leftV[1]>0) {
                sum += leftV[1];
            }
        }
        if(node.right!=null) {
            int[] rightV = getSum(node.right, max);
            rightSum = rightV[1] + node.val;
            if(rightV[0]>max) {
                max = rightV[0];
            }
            if(rightV[1]>0) {
                sum += rightV[1];
            }
        }
        if(leftSum>vals[1]) {
            vals[1] = leftSum;
        }
        if(rightSum>vals[1]) {
            vals[1] = rightSum;
        }
        if(sum>max) {
            vals[0] = sum;
        } else {
            vals[0] = max;
        }
        return vals;
    }
}


public class Solution {
   
    private int maxSum = 0;
   
    public int maxPathSum(TreeNode root) {
        if(root==null) return 0;
        maxSum = root.val;
        getPathSum(root);
        return maxSum;
    }
   
    private int[] getPathSum(TreeNode root) {
        int[] sums = new int[2];           
        sums[0] = root.val;
        sums[1] = root.val;
        if(root.left==null && root.right==null) {
            maxSum = Math.max(maxSum, root.val);
            return sums;
        }
        if(root.left!=null) {
            int[] leftSum = getPathSum(root.left);
            sums[0] = Math.max(0, Math.max(leftSum[0], leftSum[1])) + root.val;
        }
        if(root.right!=null) {
            int[] rightSum = getPathSum(root.right);
            sums[1] = Math.max(0, Math.max(rightSum[0], rightSum[1])) + root.val;
        }
        maxSum = Math.max(maxSum, Math.max(sums[0]+sums[1]-root.val, Math.max(sums[0], sums[1])));
        return sums;
    }
}


===========

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   
    int max = Integer.MIN_VALUE;
   
    public int maxPathSum(TreeNode root) {
        max = Integer.MIN_VALUE;
        helper(root);
        return max;
    }
   
    private int helper(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(0, helper(node.left));
        int right = Math.max(0, helper(node.right));
       
        max = Math.max(max, left + right + node.val);
       
        return node.val + Math.max(left, right);
    }
}

Leetcoder - Valid Palindrome

 Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.


public class Solution {
    public boolean isPalindrome(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s.isEmpty()) {
            return true;
        }
        int left = 0;
        int right = s.length()-1;
        s = s.toLowerCase();
        loop: while(left<right) {
            while(!(s.charAt(left)>='a' && s.charAt(left)<='z') && !(s.charAt(left)>='0' && s.charAt(left)<='9')) {
                left++;
                if(left>=right) {
                    break loop;
                }
            }
            while(!(s.charAt(right)>='a' && s.charAt(right)<='z') && !(s.charAt(right)>='0' && s.charAt(right)<='9')) {
                right--;
                if(right<=left) {
                    break;
                }
            }
            if(s.charAt(left)!=s.charAt(right)) {
                return false;
            } else {
                left++;
                right--;
            }
        }
        return true;
    }
}
===========

public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return true;
        }
        int start = 0;
        int end = s.length() - 1;
        s = s.toLowerCase();
        while (start <= end) {
            while (start <= end && !Character.isLetterOrDigit(s.charAt(start))) {
                start += 1;
            }
            while (start <= end && !Character.isLetterOrDigit(s.charAt(end))) {
                end --;
            }
            if (start <= end) {
                if (s.charAt(start) == s.charAt(end)) {
                    start += 1;
                    end -= 1;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

Leetcoder - Word Ladder

 Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
        // Start typing your Java solution below
        // DO NOT write main() function
// breadth first, graph search, find the shortest path
dict.remove(start);
dict.add(end);

ArrayList<String> fronties = new ArrayList<String>();
fronties.add(start);

boolean find = false;
int level = 1;
loop: while (true) {
level++;
HashSet<String> newFronties = new HashSet<String>();
for (String str : fronties) {
ArrayList<String> nexts = new ArrayList<String>();
for (int i = 0; i < str.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (str.charAt(i) != c) {
StringBuilder sb = new StringBuilder();
sb.append(str.subSequence(0, i)).append(c)
.append(str.substring(i + 1));
if (dict.contains(sb.toString())) {
nexts.add(sb.toString());
}
}
}
}
for (String next : nexts) {
if (next.equals(end)) {
break loop;
} else {
newFronties.add(next);
}
}
}
if (fronties.size() == 0) {
   level = 0;
break;
}
dict.removeAll(newFronties);
fronties.clear();
fronties.addAll(newFronties);
}
return level;
}
}


public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        ArrayList<String> frontie = new ArrayList<String>();
        frontie.add(start);
        int step = 1;
        dict.add(end);
        while(frontie.size()!=0 && dict.size()!=0) {
            ArrayList<String> newFrontie = new ArrayList<String>();
            for(String str : frontie) {
                for(int i=0;i<str.length();i++) {
                    int c = str.charAt(i);
                    for(int j='a';j<'z';j++) {
                        if(j==c) continue;
                        String newStr = str.substring(0,i) + ((char) j) + str.substring(i+1);
                        if(dict.contains(newStr)) {
                            if(newStr.equals(end)) return step+1;
                            dict.remove(newStr);
                            newFrontie.add(newStr);
                        }
                    }
                }
            }
            frontie = newFrontie;
            step++;
        }
        return 0;
    }
}

===============

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        Queue<String> queue = new LinkedList<String>();
        queue.add(beginWord);
        int step = 2;
        while (queue.size() != 0 && wordDict.size() != 0) {
            int count = queue.size();
            while (count-- > 0) {
                String str = queue.poll();
                char cs[] = str.toCharArray();
                for (int i = 0; i < str.length(); i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == str.charAt(i)) {
                            continue;
                        }
                        cs[i] = c;
                        String next = new String(cs);
                        if (next.equals(endWord)) {
                            return step;      
                        }
                        if (wordDict.contains(next)) {
                            wordDict.remove(next);
                            queue.add(next);
                        }
                    }
                    cs[i] = str.charAt(i);
                }
            }
            step++;
        }
        return 0;
    }
}

Leetcoder - Word Ladder II

 Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end,
HashSet<String> dict) {
// breadth first, graph search, find the shortest path
dict.remove(start);
dict.add(end);
HashMap<String, ArrayList<String>> backTrack = new HashMap<String, ArrayList<String>>();

ArrayList<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
ArrayList<String> fronties = new ArrayList<String>();
fronties.add(start);

boolean find = false;
while (true) {
HashSet<String> newFronties = new HashSet<String>();
for (String str : fronties) {
HashSet<Integer> skip = new HashSet<Integer>();
    if(backTrack.containsKey(str)) {
for(String p : backTrack.get(str)) {
for(int i=0;i<p.length();i++) {
if(p.charAt(i)!=str.charAt(i)) {
skip.add(i);
}
}
}
}
                ArrayList<String> nexts = new ArrayList<String>();
    for (int i = 0; i < str.length(); i++) {
if(skip.contains(i)) {
continue;
}
for (char c = 'a'; c <= 'z'; c++) {
if (str.charAt(i) != c) {
StringBuilder sb = new StringBuilder();
sb.append(str.subSequence(0, i)).append(c)
.append(str.substring(i + 1));
if (dict.contains(sb.toString())) {
nexts.add(sb.toString());
}
}
}
}
for (String next : nexts) {
ArrayList<String> preNode = backTrack.get(next);
if (preNode == null) {
preNode = new ArrayList<String>();
backTrack.put(next, preNode);
}
preNode.add(str);
if (next.equals(end)) {
find = true;
} else {
newFronties.add(next);
}
}
}
if (find || fronties.size() == 0) {
break;
}
dict.removeAll(newFronties);
fronties.clear();
fronties.addAll(newFronties);
}
if (find) {
ArrayList<String> initPath = new ArrayList<String>();
initPath.add(end);
this.findPath(initPath, backTrack, paths, end);
}
return paths;
}

private void findPath(ArrayList<String> tmp, HashMap<String, ArrayList<String>> backTrack,
ArrayList<ArrayList<String>> paths, String next) {
ArrayList<String> parents = backTrack.get(next);
if (parents != null) {
for (String p : parents) {
tmp.add(p);
this.findPath(tmp, backTrack, paths, p);
tmp.remove(tmp.size()-1);
}
} else {
ArrayList<String> path = new ArrayList<String>();
for(int i=tmp.size()-1;i>=0;i--) {
path.add(tmp.get(i));
}
paths.add(path);
}
}
}




=============


public class Solution {
    public List<List<String>> findLadders(String start, String end, Set<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        if (start == null || end == null || wordList == null || wordList.size() == 0) {
            return res;
        }
        HashMap<String, List<String>> map = new HashMap<>();
        wordList.add(end);
        HashSet<String> queue = new HashSet<String>();
        queue.add(start);
        boolean find = false;
        while (!queue.isEmpty() && !wordList.isEmpty() && !find) {
            int count = queue.size();
            HashSet<String> nextLevel = new HashSet<String>();
            for (String word : queue) {
                for (int i = 0; i < word.length(); i++) {
                    char cs[] = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (word.charAt(i) == c) {
                            continue;
                        }
                        cs[i] = c;
                        String nextWord = new String(cs);
                        if (end.equals(nextWord)) {
                            find = true;
                        }
                        if (wordList.contains(nextWord)) {
                            List<String> pres = map.get(nextWord);
                            if (pres == null) {
                                pres = new ArrayList<String>();
                                map.put(nextWord, pres);
                            }
                            pres.add(word);
                            nextLevel.add(nextWord);
                        }
                    }
                    cs[i] = word.charAt(i);
                }
            }
            for (String str : nextLevel) {
                wordList.remove(str);
            }
            queue = nextLevel;
        }
        if (!find) {
            return res;
        }
        helper(start, map, new ArrayList<String>(), end, res);
        return res;
    }
   
    private void helper(String start, HashMap<String, List<String>> map, List<String> curList, String word, List<List<String>> res) {
        if (word.equals(start)) {
            List<String> newList = new ArrayList<String>(curList);
            newList.add(word);
            Collections.reverse(newList);
            res.add(newList);
        } else {
            curList.add(word);
            List<String> pres = map.get(word);
            for (String pre : pres) {
                helper(start, map, curList, pre, res);
            }
            curList.remove(curList.size() - 1);
        }
    }
}

Leetcoder - Longest Consecutive Sequence

 Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.


public class Solution {
    public int longestConsecutive(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        HashMap<Integer, int[]> cache = new HashMap<Integer, int[]>();
        int max = 0;
        for(int n : num) {
            if(cache.containsKey(n)) {
                continue;
            }
            int[] mid = new int[2];
            boolean hasLeft = false;
            boolean hasRight = false;
            int leftBound = 0;
            int rightBound = 0;
            if(cache.containsKey(n-1)) {
                int low = cache.get(n-1)[0];
                mid[0] = low+1;
                leftBound = n - low -1;
                hasLeft = true;
            }
            if(cache.containsKey(n+1)) {
                int high = cache.get(n+1)[1];
                mid[1] = high+1;
                rightBound = n + high + 1;
                hasRight = true;
            }
            if(hasLeft) {
                cache.get(leftBound)[1] += mid[1] + 1;
            }
            if(hasRight) {
                cache.get(rightBound)[0] += mid[0] + 1;
            }
            cache.put(n, mid);
            if(mid[0]+mid[1]+1>max) {
                max = mid[0] + mid[1]+1;
            }
        }
        return max;
    }
}

public class Solution {
    public int longestConsecutive(int[] num) {
        int longest = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0;i < num.length;i++){
            // if there is no duplicates, these two lines can be commented
            if(map.containsKey(num[i])) continue;
            map.put(num[i],1);

            int end = num[i];
            int begin = num[i];
            if(map.containsKey(num[i]+1))
                end = num[i] + map.get(num[i]+1);
            if(map.containsKey(num[i]-1))
                begin = num[i] - map.get(num[i]-1);
            longest = Math.max(longest, end-begin+1);
            map.put(end, end-begin+1);
            map.put(begin, end-begin+1);
        }
        return longest;
    }
}

=========

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // the max length of the sequence containing this element
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int max = 1;
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            if (map.containsKey(n)) {
                continue;
            }
            int start = n;
            int end = n;
           
            if (map.containsKey(n + 1)) {
                end = map.get(n + 1) + n;
            }
            if (map.containsKey(n - 1)) {
                start = n - map.get(n - 1);
            }
            int len = end - start + 1;
            max = Math.max(max, len);
            map.put(start, len);
            map.put(end, len);
            map.put(n, len);
        }
        return max;
    }
}

Leetcoder - Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumNumbers(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root==null) {
            return 0;
        }
        return getSum(root, 0, 0);
    }
   
    public int getSum(TreeNode node, int currentVal, int sum) {
        currentVal = currentVal * 10 + node.val;
        if(node.left==null && node.right==null) {
            sum += currentVal;
        }
        if(node.left!=null) {
            sum = getSum(node.left, currentVal, sum);
        }
        if(node.right!=null) {
            sum = getSum(node.right, currentVal, sum);
        }
        return sum;
    }
}

Leetcoder - Surrounded Regions

 Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region .
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

public class Solution {
 
    public void visit(int i, int j, char[][] board, boolean visited[][], boolean exempt[][], Stack<int[]> tovisit) {
        if(i<0 || i>=row || j<0 || j>=column) {
            return;
        }
        if(visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        if(board[i][j] == 'O') {
            int cell[] = new int[2];
            cell[0] = i;
            cell[1] = j;
            tovisit.add(cell);
            exempt[i][j] = true;
        }
    }
 
    int row;
    int column;
 
    public void solve(char[][] board) {
        // Start typing your Java solution below
        // DO NOT write main() function
        // O in 4 boards cannot be captured
        row = board.length;
        if(row==0) {
            return;
        }
        column = board[0].length;
        if(column==0) {
            return;
        }
        boolean[][] visited = new boolean[row][column];
     
        boolean[][] exempt = new boolean[row][column];
     
        Stack<int[]> tovisit = new Stack<int[]>();
     
        for(int i=0;i<row;i++) {
            visit(i, 0, board, visited, exempt, tovisit);
            visit(i, column-1, board, visited, exempt, tovisit);
        }
     
        for(int j=1;j<column-1;j++) {
            visit(0, j, board, visited, exempt, tovisit);
            visit(row-1, j, board, visited, exempt, tovisit);
        }
     
        while(!tovisit.isEmpty()) {
            int[] cell = tovisit.pop();
            int i = cell[0];
            int j = cell[1];
            visit(i+1, j, board, visited, exempt, tovisit);
            visit(i-1, j, board, visited, exempt, tovisit);
            visit(i, j+1, board, visited, exempt, tovisit);
            visit(i, j-1, board, visited, exempt, tovisit);
        }
     
        for(int i=0;i<row;i++) {
            for(int j=0;j<column;j++) {
                if(board[i][j]=='O' && !exempt[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }
}



public class Solution {
    public void solve(char[][] board) {
        if(board==null || board.length==0 || board[0].length==0) return;
        int m = board.length;
        int n = board[0].length;
       
        for(int i=0;i<m;i++) {
            if(board[i][0]=='O') bfs(board, i, 0);
            if(board[i][n-1]=='O') bfs(board, i, n-1);
        }
       
        for(int j=0;j<n;j++) {
            if(board[0][j]=='O') bfs(board, 0, j);
            if(board[m-1][j]=='O') bfs(board, m-1, j);
        }
       
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(board[i][j]=='+') board[i][j] = 'O';
                else if(board[i][j]=='O') board[i][j] = 'X';
            }
        }
    }
   
    private void bfs(char[][] board, int i, int j) {
        board[i][j] = '+';
        LinkedList<int[]> lst = new LinkedList<int[]>();
        int m = board.length;
        int n = board[0].length;
        int[] idx = new int[2];
        idx[0] = i;
        idx[1] = j;
        lst.add(idx);
        while(lst.size()!=0) {
            int[] tmp = lst.removeFirst();
            int x = tmp[0];
            int y = tmp[1];
            add(x-1, y, board, lst);
            add(x+1, y, board, lst);
            add(x, y-1, board, lst);
            add(x, y+1, board, lst);
        }
    }
   
    private void add(int i, int j, char[][] board, LinkedList<int[]> lst) {
        int m = board.length;
        int n = board[0].length;
        if(i<0 || i>=m || j<0 || j>=n || board[i][j]!='O') return;
        int[] idx = new int[2];
        idx[0] = i;
        idx[1] = j;
        lst.addFirst(idx);
        board[i][j] = '+';
    }
}


========================================================

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        int row = board.length;
        int column = board[0].length;
       
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') {
                tag(board, i, 0);
            }
            if (board[i][column - 1] == 'O') {
                tag(board, i , column - 1);
            }
        }
        for (int i = 1; i < column - 1; i++) {
            if (board[0][i] == 'O') {
                tag(board, 0, i);
            }
            if (board[row - 1][i] == 'O') {
                tag(board, row - 1, i);
            }
        }
       
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (board[i][j] == '+') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
   
    private void tag(char[][] board, int i, int j) {
        int row = board.length;
        int column = board[0].length;
        if (board[i][j] == 'O') {
            board[i][j] = '+';
            if (i - 1 > 0) tag(board, i - 1, j);
            if (i + 1 < row) tag(board, i + 1, j);
            if (j - 1 > 0) tag(board, i, j - 1);
            if (j + 1 < column) tag(board, i, j + 1);
        }
    }
}

Leetcoder - Distinct Subsequences (DP)

 Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.


public class Solution {
    public int numDistinct(String S, String T) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(S.length()<T.length()) {
            return 0;
        }
        int c[][] = new int[S.length()][T.length()];

        if(S.charAt(0)==T.charAt(0)) {
            c[0][0] = 1;
        }
        for(int i=1;i<S.length();i++) {
            c[i][0] = c[i-1][0];
            if(S.charAt(i)==T.charAt(0)) {
                c[i][0]++;
            }
        }
     
        for(int j=1;j<T.length();j++) {
            for(int i=j;i<S.length();i++) {
                if(S.charAt(i)==T.charAt(j)) {
                    c[i][j] = c[i-1][j] + c[i-1][j-1];
                } else {
                    c[i][j] = c[i-1][j];
                }
            }
        }
        return c[S.length()-1][T.length()-1];
    }
}

====================

public class Solution {
    public int numDistinct(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        int dp[][] = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j -1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len1][len2];
    }
}

Leetcoder - Distinct Subsequences (recursion)

 Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.


public class Solution {
    public int numDistinct(String S, String T) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> positions = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<T.length();i++) {
            char c = T.charAt(i);
            ArrayList<Integer> position = new ArrayList<Integer>();
            for(int j = 0;j<S.length();j++) {
                char c2 = S.charAt(j);
                if(c2==c) {
                    position.add(j);
                }
            }
            if(position.size()==0) {
                return 0;
            }
            Collections.reverse(position);
            positions.add(position);
        }
        return permuate(positions, 0, -1, 0);
    }
 
    private int permuate(ArrayList<ArrayList<Integer>> positions, int idx, int last, int amount) {
        ArrayList<Integer> position = positions.get(idx);
        for(int p : position) {
            if(p>last) {
                if(idx==positions.size()-1) {
                    amount++;
                } else {
                    amount = permuate(positions, idx+1, p, amount);
                }
            } else {
            break;
            }
        }
        return amount;
    }
}

Can't go through the time limit...Need DP...

Leetcoder - Palindrome Partitioning

 Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

public class Solution {
    public ArrayList<ArrayList<String>> partition(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        HashMap<Integer, ArrayList<ArrayList<String>>> groups = new HashMap<Integer, ArrayList<ArrayList<String>>>();
     
        ArrayList<ArrayList<String>> group0 = new ArrayList<ArrayList<String>>();
        ArrayList<String> t = new ArrayList<String>();
        t.add(s.substring(0, 1));
        group0.add(t);
        groups.put(0, group0);
        boolean cache[][] = new boolean[s.length()][s.length()];
        for(int i=1;i<s.length();i++) {
            ArrayList<ArrayList<String>> newGroup = new ArrayList<ArrayList<String>>();
            String sub = s.substring(i, i+1);
            for(ArrayList<String> tuple : groups.get(i-1)) {
                 ArrayList<String> newTuple = new ArrayList<String>(tuple);
                 newTuple.add(sub);
                 newGroup.add(newTuple);
            }
            for(int j=i-1;j>=0;j--) {
                if(s.charAt(i)==s.charAt(j) && (cache[i-1][j+1] || j>=i-2)) {
                    cache[i][j] = true;
                    ArrayList<ArrayList<String>> tmp = null;
                    sub = s.substring(j, i+1);
                    if(j==0) {
                        ArrayList<String> newTuple = new ArrayList<String>();
                        newTuple.add(sub);
                        newGroup.add(newTuple);
                    } else {
                        tmp = groups.get(j-1);
                        for(ArrayList<String> tuple : tmp) {
                            ArrayList<String> newTuple = new ArrayList<String>(tuple);
                            newTuple.add(sub);
                            newGroup.add(newTuple);
                        }
                    }
                }
            }
            groups.put(i, newGroup);
        }
        return groups.get(s.length() - 1);
    }
}
========

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null || s.isEmpty()) return res;
        helper(s, 0, new ArrayList<>(), res);
        return res;
    }
   
    private void helper(String s, int p, List<String> list, List<List<String>> res) {
        if (p == s.length()) {
            res.add(new ArrayList<>(list));
        } else {
            for (int i = p; i < s.length(); i++) {
                String sub = s.substring(p, i + 1);
                if (isPalin(sub)) {
                    list.add(sub);
                    helper(s, i + 1, list, res);
                    list.remove(list.size() - 1);
                }
            }
        }
    }
   
    private boolean isPalin(String sub) {
        int s = 0;
        int e = sub.length() - 1;
        while (s <= e) {
            if (sub.charAt(s) == sub.charAt(e)) {
                s++;
                e--;
            } else {
                return false;
            }
        }
        return true;
    }
}

Leetcode - Palindrome Partitioning II

 Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.


public class Solution {
   
    public int minCut(String s) {
        int cuts[] = new int[s.length()];
        cuts[0] = 0;
        boolean cache[][] = new boolean[s.length()][s.length()];
        for (int i = 1; i < s.length(); i++) {
            cuts[i] = cuts[i-1]+1;
            for (int j = i - 1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j)
                        && (cache[j+1][i - 1] || j>=i-2)) {
                    cache[j][i] = true;
                    if(j==0) {
                        cuts[i] = 0;
                    } else {
                        cuts[i] = Math.min(cuts[i], cuts[j-1] + 1);
                    }
                }
            }
        }
        return cuts[s.length() - 1];
    }
}


============

public class Solution {
    public int minCut(String s) {
        if(s.length()==0)return 0;
        int[] c=new int[s.length()+1];
        for(int i=0;i<s.length();i++) {
            c[i]=Integer.MAX_VALUE;
        }
        c[s.length()]=-1;
        for(int i=s.length()-1;i>=0;i--){
            for(int a=i,b=i;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a--,b++) c[a]=Math.min(c[a],1+c[b+1]);
            for(int a=i,b=i+1;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a--,b++) c[a]=Math.min(c[a],1+c[b+1]);
        }
        return c[0];
    }
}