Han Zhu's Study Notes

Given a  non-empty  string  s  and a dictionary  wordDict  containing a list of  non-empty  words, determine if  s  can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words. For example, given s  =  "leetcode" , dict  =  ["leet", "code"] . Return true because  "leetcode"  can be segmented as  "leet code" . UPDATE (2017/1/4): The  wordDict  parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes. Thought process: Sub-problem: determine if a substring of s can be segmented into a sequence of one or more dictionary words. Function: f[i] = if there exists (f[j] && s[j, i] is a dictionary word). Initialization: f[0] = true. Add a dummy character at the start of the string. Answer: f[s.length]. Sol...

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. Thought process: Sub-problem: find the minimum cuts needed for a palindrome partitioning of a substring of s. Function: f[i] = min(f[j]) + 1, where j < i and s[j, i] is a palindrome. Initialization: if there's only one character in the string, it requires no cut. So we set f[0] = -1 and f[1] will become 0. Further calculations where the whole string is a palindrome will also be easier. Answer: f[s.length]. How to check whether a substring is a palindrome? The loop takes O(n^2) already. If we check if a string is a palindrome inside the loop, the overall time complexity will increase to O(n^3). To reduce the time complexity...

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A =  [2,3,1,1,4] The minimum number of jumps to reach the last index is  2 . (Jump  1  step from index 0 to 1, then  3  steps to the last index.) Note: You can assume that you can always reach the last index. Thought process: Since we can assume that we can always reach the last index, we know that every index can be reached. Sub-problem: reach any index in the minimum number of jumps. Formula: f[i] = min(f[j]) + 1, where 0 <= j < i and j + jumps[j] >= i. Initialization: f[0] = 0. We don't need to jump at all to reach the first index. Answer: f[last index]. Here we can also be greedy. If indexes a and b can both jump to c and a < b, then we...

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A =  [2,3,1,1,4] , return  true . A =  [3,2,1,0,4] , return  false . Thought process: Sub-problem: if you are able to reach any index. Formula: f[i] = (f[0] && 0 + jump[0] >= i) || (f[1] && 1 + jump[1] >= i) || . . . || (f[i - 1] && i - 1 + jump[i - 1] >= i). Initialization: f[0] = true. Answer: f[last index]. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class Solution { public boolean canJump ( int [] nums ) { int length = nums . length ; boolean [] f = new boolean [ length ]; f [ 0 ] = true ; for ( int i = 1 ; i < length ; ...

You are climbing a stair case. It takes  n  steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note:  Given  n  will be a positive integer. Thought process: Sub-problem: in how many distinct ways can you climb to any step? Formula: f[i] = f[i - 1] + f[i - 2]. Initialization: f[0] = f[1] = 1. Answer: f[n]. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class Solution { public int climbStairs ( int n ) { int [] f = new int [ n + 1 ]; f [ 0 ] = 1 ; f [ 1 ] = 1 ; for ( int i = 2 ; i <= n ; i ++) { f [ i ] = f [ i - 1 ] + f [ i - 2 ]; } return f [ n ]; } } Time complexity: O(n).

Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as  1  and  0  respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. [ [0,0,0], [0,1,0], [0,0,0] ] The total number of unique paths is  2 . Note:   m  and  n  will be at most 100. Thought process: Sub-problem, initialization, and answer are the same as "62. Unique Paths" . Formula: f[i][j] = f[i - 1][j] + f[i][j - 1] if grid[i][j] == 0; 0 otherwise. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 public class Solution { public int uniquePathsWithObstacles ( int [][] obstacleGrid ) { int height = obstacleGrid . length ; if ( height == 0 ) { return 0 ; } ...

A robot is located at the top-left corner of a  m  x  n  grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? Above is a 3 x 7 grid. How many possible unique paths are there? Note:   m  and  n  will be at most 100. Thought process: Sub-problem: how many unique paths are there from top-left corner to any point. Formula: f[i][j] = f[i - 1][j] + f[i][j - 1]. Initialization: there is only one path from top-left corner to a point on the first row or column. Answer: f[m - 1][n - 1]. Solution 1 (DP): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int uniquePaths ( int m , int n ) { if ( m == 0 || n == 0 ) { return 0 ; } ...