Interleaving Strings

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Solution: using DP. This question is very similar to "Find all path", you can just imagine, taking string1 is just as going down, and taking string2 is like to going right.

Java语言: InterleavingString

01 public boolean isInterleave(String s1, String s2, String s3) {
02     int m=s1.length();
03     int n=s2.length();
04     int len=s3.length();
05     if(m+n!=len)
06         return false;
07     if(m==0)
08         return s2.equals(s3);
09     if(n==0)
10         return s1.equals(s3);
11     //DP approach, initiate a 2D array to store 
12     //the validity of the interleaving to the current point
13     boolean [][]array=new boolean[m+1][n+1];
14     for(int i=1;i<=m;i++)
15     {
16         if(s1.charAt(i-1)==s3.charAt(i-1))
17         {
18             array[i][0]=true;
19         }
20     }
21     for(int j=1;j<=n;j++)
22     {
23         if(s2.charAt(j-1)==s3.charAt(j-1))
24         {
25             array[0][j]=true;
26         }
27     }
28     for(int i=1;i<=m;i++)
29     {
30         for(int j=1;j<=n;j++)
31         {
32             //take character from s1
33             if(s1.charAt(i-1)==s3.charAt(i+j-1) && array[i-1][j]==true)
34                 array[i][j]=true;
35             //take character from s2    
36             if(s2.charAt(j-1)==s3.charAt(i+j-1) && array[i][j-1]==true)
37                 array[i][j]=true;
38         }
39     }
40     return array[m][n];
41 }

Distinct Subsequences

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.

Solution: using dynamic programming. Initiating a two dimensional array of m*n, where n and m are the lengths of S and T respectively. An array entry array[i][j] indicate the number of subsequences of the first i characters in T, within the first j characters in S. 

First, initiating the first line. The if S.charAt(0) and T.charAt(0) is the same, the first entry of array should be 1. Then we look if the first character of T appear again in S. If so, we increment the value of the entry by one.

2. The first column except array[0][0] should all be 0.

3. Then, updating the inside elements.

     if the ith character of T is the same as the jth character of S, a new match occurs. array[i][j] is calculated by summing up the entry in its left up cell (indicating the condition before handling the current characters in both array) and the entry in its left cell (indicating the matching before introducing the current character in array S).

If they are not the same, just copy the number from its left cell, indicating there is no new match.

4. In the end, simply return array[n-1][m-1].

     r  a  b  b  b  i  t

r   1  1  1  1  1  1  1
a   0  1  1  1  1  1  1
b   0  0  1  2  3  3  3

b   0  0  0  1  3  3  3

i    0  0  0  0  0  3  3
t    0  0  0  0  0  0  3

Java语言: DistinctSubsequences

01 public int numDistinct(String S, String T) {
02     int m=S.length();
03     int n=T.length();
04   
05     if(m==0 || n==0)
06         return 0;
07     // use dp, set up a two dimensional array to keep the temporal result
08     int[][] array=new int[n][m];
09     //initiate the result of comparing first characters
10     if(S.charAt(0)==T.charAt(0))
11     {
12         array[0][0]=1;
13     }
14     //initiate the first line
15     for(int j=1;j< m; j++)
16     {
17         if(S.charAt(j)==T.charAt(0))
18         {
19             array[0][j]=array[0][j-1]+1;
20         }
21         else
22         {
23             array[0][j]=array[0][j-1];
24         }
25     }      
26     //keep going through each character
27     //if two characters are same, result is the current number
28     //+ previous number of matched sequence before this character
29     // otherwise, keep the current number
30     for(int i=1;i<n;i++)
31     {
32         for(int j=1;j<m;j++)
33         {
34             if(T.charAt(i)==S.charAt(j))
35             {
36                 array[i][j]=array[i-1][j-1]+array[i][j-1];
37             }
38             else
39             {
40                 array[i][j]=array[i][j-1];
41             }
42         }
43     }
44   
45     return array[n-1][m-1];
46 }

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Hint: this is a typical dynamic programming question. At a moment, the distance between two words is calculated by adding a new value to some previous values. This can be done by inserting the last character, or deleting the last character, or by replacing the last character. If the last characters are the same, the replace cost 0. All other operations cost one. Therefore, we just choose the minimum from all three possible values.

01 public int minDistance(String word1, String word2) {
02     if(word1.length()==0)   return word2.length();
03     if(word2.length()==0)   return word1.length();
04     int m=word1.length();
05     int n=word2.length();
06   
07     //Use DP, initiate an array to store previous distance values.
08     int [][] array=new int [m+1][n+1];
09   
10     for(int i=0;i<=m;i++)
11     {
12         array[i][0]=i;
13     }
14   
15     for(int j=0;j<=n;j++)
16     {
17         array[0][j]=j;
18     }
19   
20     for(int i=1;i<=m;i++)
21     {
22         for(int j=1;j<=n;j++)
23         {
24             int value=(word1.charAt(i-1)==word2.charAt(j-1))? 0 : 1;
25             array[i][j]=findMin(array[i-1][j]+1,array[i][j-1]+1,array[i-1][j-1]+value);
26         }
27     }
28   
29     return array[m][n];
30 }
31 
32 public int findMin(int a, int b, int c)
33 {
34   
35     if(a<b)
36     {
37         if(a<c)
38         {
39            return a;
40         }
41       
42         else
43         {
44             return c;
45         }
46     }
47     else
48     {
49         if(c<b)
50             return c;
51         else
52             return b;
53     }
54 }

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Hint: use dynamic programming. However, instead of using n arrays which in total cost n^2 space, we just use 2 arrays interchangeably to store the minimum path sum until the current row.

01 public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
02     // Start typing your Java solution below
03     // DO NOT write main() function
04     int size=triangle.size();
05     if(size==0)
06         return 0;
07     //get the numbers of each row in the original triangle
08     ArrayList<Integer> row=triangle.get(0);
09   
10     //keeps the minimum path sum to reach each node of the current line
11     //starts from the 0-th line
12     ArrayList<Integer> al=new ArrayList<Integer>();
13     al.add(row.get(0));
14     if(size==1)
15         return al.get(0);
16   
17     //Iterate from the 1-st line
18     for(int i=1;i<size;i++)
19     {
20        //keep the numbers of the previous line in al
21        //use another array al2 to calculate the new path sum
22        //then copy the new result in al2 back to al
23         ArrayList<Integer> al2=new ArrayList<Integer>();
24         for(int k=0;k<al.size();k++)
25         {
26             al2.add(al.get(k));
27         }
28       
29         row=triangle.get(i);          
30         int lmost=row.get(0)+al.get(0);
31         al2.set(0,lmost);
32         for(int j=1;j<i;j++)
33         {
34             //minimum of the left index and itself in the previous line
35             //plus its own value
36             int value=Math.min(al.get(j-1),al.get(j))+row.get(j);
37             al2.set(j,value);
38         }
39         int rmost=al.get(i-1)+row.get(i);
40         al2.add(rmost);
41         al=al2;
42     }
43   
44     //find min
45     int min=al.get(0);
46     for(int i=0;i<al.size();i++)
47     {
48         if(al.get(i)<min)
49         {
50             min=al.get(i);
51         }
52     }
53   
54     return min;
55           
56 }

Jump Game

Jump GameMar 25 '12

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.

Solution 1: 
You can treat it as a dynamic programming question. If you want to know whether you can jump to the end from the current node, you should know the situations in the positions that the current nodes can go through one jump. Then do it backwards.

01 public boolean canJump(int[] A) {

02     int len=A.length;

03     boolean [] results=new boolean [len];

04     results[len-1]=true;

05     for(int i=len-2;i>=0;i--)

06     {

07         int value=A[i];

08         if(value+i>=len-1)

09         {

10             results[i]=true;

11         }

12         else

13         {

14             for(int j=1;j<=value;j++)

15             {

16                 if(results[i+j]==true)

17                 {

18                     results[i]=true;

19                     break;

20                 }

21             }

22           

23         }

24       

25     }

26     return results[0];

27 }

Solution 2:
Instead using DP, we can use greedy. Calculate the farthest position it can jumps to. If the farthest position is greater than or equal to the last index of the array, return true, else return false.

01 public boolean canJump(int[] A) {
02     int farthest=A[0];
03     int i=1;
04     while(i<=farthest && i<A.length)
05     {
06         if(A[i]+i>farthest)
07         {
08             farthest=A[i]+i;
09         }
10         i++;
11     }
12     if(farthest>=A.length-1)
13         return true;
14     else
15         return false;
16 }

Unique Path II

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.

01 public int uniquePathsWithObstacles(int[][] obstacleGrid) {

02    int m=obstacleGrid.length;
03    if(m==0)
04        return 0;
05    int n=obstacleGrid[0].length;
06    if(n==0)
07        return 0;
08    int [][]results=new int[m][n];
09    if(obstacleGrid[0][0]==0)
10    {
11        results[0][0]=1;
12    }
13      
14    else
15    {
16        results[0][0]=0;
17    }
18      
19    for(int i=1;i<m;i++)
20    {
21        if(obstacleGrid[i][0]==0)
22        {
23            results[i][0]=results[i-1][0];
24        }
25        else
26        {
27            results[i][0]=0;
28        }
29    }
30    for(int j=1;j<n;j++)
31    {
32        if(obstacleGrid[0][j]==0)
33        {
34            results[0][j]=results[0][j-1];
35        }
36        else
37        {
38            results[0][j]=0;
39        }
40      
41    }
42  
43    for(int i=1;i<m;i++)
44    {
45        for(int j=1;j<n;j++)
46        {
47            if(obstacleGrid[i][j]==0)
48            {
49                results[i][j]=results[i-1][j]+results[i][j-1];
50            }
51            else
52            {
53                results[i][j]=0;
54            }
55        }
56    }
57    return results[m-1][n-1];
58 }