LeetCode WordBreak II

This is the extension of word break problem.
Add traceback for the solution.

public List<String> wordBreak(String s, Set<String> dict) {
        int len = s.length();
        boolean[] dp = new boolean[len+1];
        List<List<Integer>> prevs = new ArrayList<List<Integer>>();
        for (int i=0; i<=len; i++) {
            prevs.add(new ArrayList<Integer>());
        }
        dp[0] = true;
        for (int i=1; i<=len; i++) {
            for (int j=0; j<i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    prevs.get(i).add(j);
                    dp[i]=true;
                }
            }
        }
        List<String> res = new ArrayList<String>();
        buildRes(s, prevs, len, res, "");
        return res;
    }
   
    private void buildRes(String s, List<List<Integer>> prevs, int end, List<String> res, String curr) {
        List<Integer> prev = prevs.get(end);
        for (int i=0; i<prev.size(); i++) {
            int newEnd = prev.get(i);
            String sub = s.substring(newEnd, end);
            String r = sub;
            if (!curr.equals("")) {
                r = r + " " + curr;
            }
            if (newEnd == 0) {
                res.add(r);
            } else {
                buildRes(s, prevs, newEnd, res, r);
            }
           
        }
    }

LeetCode Palindrome Partitioning II

DP is for recording the min cut from i to the end.
isPalindrome is for recording the palindrome between index i and j.

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

LeetCode Longest Consecutive Sequence

Use HashSet
public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
for (int i : nums) {
set.add(i);
}
int max=0;
for (int i:nums) {
int cnt = 1;
set.remove(i);
int temp = i;
while (set.contains(temp-1)) {
set.remove(temp-1);
temp--;
cnt++;
}
temp=i;
while (set.contains(temp+1)) {
set.remove(temp+1);
temp++;
cnt++;
}
max = Math.max(max, cnt);
}
return max;
}

Use HashMap
This is from Jiaxin's leetcode
http://shanjiaxin.blogspot.com/2014/04/longest-consecutive-sequence-leetcode.html

public int longestConsecutive(int[] num) {


  if (num == null || num.length == 0) {


   return 0;


  }


  


  HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();


  for (int value : num) {


   map.put(value, 0);


  }


  


  int maxLength = 1;


  for (int i : num) {


   if (map.get(i) == 1) {


    continue;


   }


   


   // Search Increasing sequence for current element(right side)


   int temp = i;


   int current_max = 1;


   while (map.containsKey(temp + 1)) {


    current_max++;


    temp++;


    map.put(temp, 1);


   }


   


   // Search Descending sequence for current element(left side)


   temp = i;


   while (map.containsKey(temp - 1)) {


    current_max++;


    temp --;


    map.put(temp, 1);


   }


   


   maxLength = Math.max(current_max, maxLength);


  }


  


  return maxLength;


    }

Flatten Binary Tree to Linked List
Recursion:
public void flatten(TreeNode root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
    flattenRecurr(root);
    }
    private TreeNode flattenRecurr(TreeNode root) {
        if (root==null || root.left==null && root.right==null) return root;
TreeNode left = root.left;
TreeNode right = root.right;
root.left=null;

if (left!=null) {
root.right=left;
root=flattenRecurr(left);
}
if (right!=null) {
root.right=right;
root=flattenRecurr(right);
}
return root;
    }


Iterative:
 public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
       
        while (p!=null || !stack.empty()) {
            if (p.right!=null) {
                stack.push(p.right);
            }
            if (p.left!=null) {
                p.right = p.left;
                p.left = null;
            } else if (!stack.empty()){
                TreeNode temp = stack.pop();
                p.right=temp;
            }
            p=p.right;
        }
    }

Same space complexity O(logn)

LeetCode Best Time to Buy and Sell Stock IV

Add the quickSolve method to avoid the corner case. When k=100000000 and array is relative small.

public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if(len == 0) {
            return 0;
        }
        if (k>=len/2) return quickSolve(prices);
       
        int[][] local = new int[len][k+1];      // local[i][j]: max profit till i day, j transactions,
                                                // where there is transaction happening on i day
        int[][] global = new int[len][k+1];     // global[i][j]: max profit across i days, j transactions
        for(int i=1; i<len; i++) {
            int diff = prices[i] - prices[i-1];
            for(int j=1; j<=k; j++) {
                local[i][j] = Math.max(global[i-1][j-1]+Math.max(diff,0), local[i-1][j]+diff);
                global[i][j] = Math.max(global[i-1][j], local[i][j]);
            }
        }
        return global[len-1][k];
    }
   
    private int quickSolve(int[] prices) {
        int len = prices.length, profit = 0;
        for (int i = 1; i < len; i++)
            // as long as there is a price gap, we gain a profit.
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }

LeetCode Distinct Subsequences

We try two possible solutions: DFS and DP

private static int disNum = 0;
public static int numDistinct(String S, String T) {
int[] flags =new int[S.length()];
int num=0;
dfs(num, flags, 0, 0, S, T);
return disNum;
}

private static void dfs(int num, int[] flags, int indexS, int indexT, String S,
String T) {
if (num==T.length()) {
disNum++;
} else {
for (int i=indexS; i<S.length(); i++) {
if (S.charAt(i)==T.charAt(indexT) && flags[i]==0) {
flags[i]=0;
num++;
dfs(num, flags, i+1, indexT+1, S, T);
flags[i]=0;
num--;
}
}
}
}

DP with 2D
public static int numDistictDP(String S, String T) {
int[][] dp = new int[T.length()+1][S.length()+1];
dp[0][0]=1;
for (int i=1; i<=S.length(); i++) {
dp[0][i]=1;
}
for (int i=1; i<=T.length(); i++) {
dp[i][0]=0;
}
for (int i=1; i<=T.length(); i++) {
for (int j=1; j<=S.length(); j++) {
if (T.charAt(i-1)==S.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
} else {
dp[i][j] = dp[i][j-1];
}
}
}
return dp[T.length()][S.length()];
}

DP with optimized space
public int numDistinctDPOptimized(String S, String T) {
       // IMPORTANT: Please reset any member data you declared, as
       // the same Solution instance will be reused for each test case.
   if(S==null || T==null) return -1;
   int[] dp = new int[T.length()+1];
   dp[0]=1;
   for(int i=0; i<S.length();i++)
       for(int j=T.length(); j>0; j--)
           dp[j] += T.charAt(j-1)!=S.charAt(i)?0:dp[j-1];
 
   return dp[T.length()];
   }

LeetCode Recover Binary Search Tree

Similar idea with using inorder traversal (Valid binary Search)

Here is the solution for valid binary search
private TreeNode prev;
    public boolean isValidBST(TreeNode root) {
       prev = null;
       return isMonoIncreasing(root);
    }
   
    private boolean isMonoIncreasing (TreeNode p) {
        if (p == null) return true;
        if (isMonoIncreasing(p.left)) {
            if (prev != null && p.val <= prev.val) return false;
            prev = p;
            return isMonoIncreasing(p.right);
        }
        return false;
    }

Here is the solution for the recover binary search
public static TreeNode prev;

    public void recoverTree(TreeNode root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
//Similar idea with isValidBST using inOrder traversal

        prev = null;
//我们知道只有2个TreeNode 被弄错了
TreeNode[] misOrder = new TreeNode[2];
inorder(root,misOrder);
int temp = misOrder[0].val;
misOrder[0].val = misOrder[1].val;
misOrder[1].val = temp;
}
private static void inorder(TreeNode root, TreeNode[] misOrder) {
if(root == null) return;

inorder(root.left, misOrder);
if(prev!=null && prev.val > root.val){
if(misOrder[0] == null) misOrder[0] = prev;
misOrder[1] = root;
}
//dont forget to update the prev
prev = root;

inorder(root.right, misOrder);
}

LeetCode InterLeaving String

DP
Firstly, we don't care about the space and find a careful memorization.
Second, optimize the space complexity.

The character is either from s1 or s2.
DP[i][j] = (s1.charAt(i-1)==s3.charAt(i+j-1) && DP[i-1][j]) || (s2.charAt(j-1)==s3.charAt(i+j-1) && DP[i][j-1]);

DP[i][j] = true;
Means s3.substring(0, i+j-1) can be displayed by s1.substring(0,i) and s2,substring(0,j)

Here is the solution.
public boolean isInterleave(String s1, String s2, String s3) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
       
      if (s1==null || s2==null || s3==null) return false;
      int len1 = s1.length(), len2 = s2.length();
      if (s1.length()+s2.length() != s3.length()) return false;
      boolean dp[][] = new boolean[len1+1][len2+1];
      dp[0][0] = true;
      for (int i=1; i<=len1;i++) {
          if (s1.charAt(i-1)==s3.charAt(i-1) && dp[i-1][0]) {
              dp[i][0] = true;
          }
      }
     
      for (int j=1; j<=len2;j++) {
          if (s2.charAt(j-1)==s3.charAt(j-1) && dp[0][j-1]) {
              dp[0][j] = true;
          }
      }
     
      for (int i=1; i<=len1; i++) {
          for (int j=1; j<=len2; j++) {
              if (s1.charAt(i-1) == s3.charAt(i+j-1) && dp[i-1][j]) {
                  dp[i][j] = true;
              }
              if (s2.charAt(j-1) == s3.charAt(i+j-1) && dp[i][j-1]) {
                  dp[i][j] = true;
              }
          }
      }
      return dp[len1][len2];

}


Follow up:

I thought I am so diao to solve the 2D dynamic programming questions.
But here is some improvement for the current method. We don't really need O(mn) space. We can only use O(n) to maintain the status like DP[][].

For better solution, we can use the shorter array to store the status. O(min(m,n)).

Here is the solution.

public boolean isInterleave(String s1, String s2, String s3) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
       
      if (s1==null || s2==null || s3==null) return false;
      int len1 = s1.length(), len2 = s2.length();
      if (s1.length()+s2.length() != s3.length()) return false;
        String minWord = s1.length()>s2.length()?s2:s1;
        String maxWord = s1.length()>s2.length()?s1:s2;
        int lenMin = minWord.length();
        int lenMax = maxWord.length();
      boolean dp[] = new boolean[lenMin+1];
      dp[0] = true;
      for (int i=0; i<lenMin;i++) {
          dp[i+1] = minWord.charAt(i)==s3.charAt(i) && dp[i];
      }
     
      for (int i=0; i<lenMax; i++) {
          dp[0] = dp[0] && maxWord.charAt(i) == s3.charAt(i);
          for (int j=0; j<lenMin; j++) {
              dp[j+1] = dp[j+1]&& maxWord.charAt(i)==s3.charAt(i+j+1) || dp[j] && minWord.charAt(j)==s3.charAt(i+j+1);
          }
      }
      return dp[lenMin];

}

LeetCode Scramble String

Recursion with some cutting

1. value
2. length
3. equals

public boolean isScramble(String s1, String s2) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (s1==null || s2==null || s1.length()!=s2.length()) return false;
        if (s1.equals(s2)) return true;
       
        int len = s1.length();
        int value1=0, value2=0;
        for (int i=0; i<len; i++) {
            value1 += s1.charAt(i) - '0';
            value2 += s2.charAt(i) - '0';
        }
        if (value1 != value2) return false;
       
        for (int i=1; i<len; i++) {
            if (isScramble(s1.substring(0,i), s2.substring(0,i)) && isScramble(s1.substring(i), s2.substring(i))) {
                return true;
            }
            if (isScramble(s1.substring(0, i), s2.substring(len-i)) && isScramble(s1.substring(i), s2.substring(0, len-i))) {
                return true;
            }
        }
        return false;
    }

DP solution: 3D DP

public boolean isScramble(String s1, String s2) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (s1==null || s2==null || s1.length()!=s2.length()) return false;
        if (s1.length()==0) return true;
        int len = s1.length();
        boolean[][][] M = new boolean[len][len][len+1];
        for (int i=0; i<len; i++) {
            for (int j=0; j<len; j++) {
                M[i][j][1] = s1.charAt(i)==s2.charAt(j);
            }
        }
       
        for (int L=2; L<=len; L++) {
            for (int i=0; i<len-L+1; i++) {
                for (int j=0; j<len-L+1; j++) {
                    for (int k=1; k<L; k++) {
                        M[i][j][L] |= M[i][j][k] && M[i+k][j+k][L-k] || M[i][j+L-k][k] && M[i+k][j][L-k];
                    }
                }
            }
        }
        return M[0][0][len];
    }