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 }

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

This question is more difficult than the first "populating next right pointers in each node", which applies to a perfect binary search tree. In contrast, this tree can be any tree. However, it is not that difficult. Just find the next node that you can point to, by looking up the neighbors on the parent node. Find the first node that has a child, and set its first child to the next of your current node.

There is one thing you need to pay attention when you do the recursive call. Remember to apply the connect function on the right child of the current node first. So that you won't loose any connection at the parent level, before you handle the child nodes.

Java语言: PopulatingNextRightII

01 public class Solution {
02     public void connect(TreeLinkNode root) {
03         if(root==null)
04             return;
05         if(root.left!=null)
06         {
07             if(root.right!=null)
08             {
09                 root.left.next=root.right;
10             }
11             else
12             {
13                 TreeLinkNode temp=root.next;
14                 //find the first non-empty neighbor on parent level
15                 while(temp!=null && temp.left==null && temp.right==null)
16                 {
17                     temp=temp.next;
18                 }
19                 if(temp!=null)
20                 {
21                     if(temp.left!=null)
22                     {
23                         root.left.next=temp.left;
24                     }
25                     else
26                     {
27                         root.left.next=temp.right;
28                     }
29                 }
30             }
31         }
32       
33         if(root.right!=null)
34         {
35             TreeLinkNode tmp=root.next;
36             while(tmp!=null && tmp.left==null && tmp.right==null)
37             {
38                 tmp=tmp.next;
39             }
40           
41             if(tmp!=null)
42             {
43                 if(tmp.left!=null)
44                 {
45                     root.right.next=tmp.left;
46                 }
47                 else
48                 {
49                     root.right.next=tmp.right;
50                 }
51             }
52           
53         }
54     
55         //Connect right tree first
56         //so that you can resolve the next pointers on parent level
57         connect(root.right);
58         connect(root.left);      
59     }
60 }

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Java语言: ValidSudoku

01 public boolean isValidSudoku(char[][] board) {
02     for(int i=0; i<9; i++)
03     {
04         boolean [] exist=new boolean[9];
05         for(int j=0;j<9;j++)
06         {
07             if(board[i][j]!='.')
08             {
09                 int value=board[i][j]-'0';
10                 if(exist[value-1]==true)
11                     return false;
12                 exist[value-1]=true;
13             }
14         }          
15     }
16   
17     for(int j=0; j<9; j++)
18     {
19         boolean [] exist=new boolean[9];
20         for(int i=0;i<9;i++)
21         {
22             if(board[i][j]!='.')
23             {
24                 int value=board[i][j]-'0';
25                 if(exist[value-1]==true)
26                     return false;
27                 exist[value-1]=true;
28             }
29         }          
30     }
31   
32     for(int m=0;m<3;m++)
33     {
34         for(int n=0;n<3;n++)
35         {
36             boolean []exist=new boolean[9];
37             for(int i=0;i<3;i++)
38             {
39                 for(int j=0;j<3;j++)
40                 {
41                     if(board[m*3+i][n*3+j]!='.')
42                     {
43                         int value=board[m*3+i][n*3+j]-'0';
44                         if(exist[value-1]==true)
45                             return false;
46                         exist[value-1]=true;
47                     }
48                 }
49             }
50         }
51     }      
52   
53     return true;
54 }

Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Solution: first of all, we can think about the brute force method. Starting at the first character of both strings, comparing the content of the two pointers. If the target string ends, we just return the starting point of the first string. If at a time the characters that two pointers pointed are not equal, we proceed to the new start position of the first string. The code is as follows,

C++语言: strStr

01 char *strStr(char *haystack, char *needle) {

02     if(*needle=='\0')

03         return haystack;

04     if(*haystack=='\0')

05         return NULL;

06     //set the start pointer to the beginning of the first string

07     char *start=haystack;

08     char *p;

09     while(*start!='\0')

10     {

11         p=start;

12         //q points to the target string

13         char *q=needle;

14         while(*p!='\0' && *q!='\0' && *p==*q)

15         {

16             p++;

17             q++;

18         }

19         //q ends, return the starting point

20         if(*q=='\0')

21         {

22             return start;

23         }

24         //update the starting position

25         start++;

26     }

27     return NULL;

28 }

However, this method is not quite efficient. If the first string does not contain the second string, the program will loop until the start pointer point to the last character of the first string. But this is not necessary. Why? Assuming that the first string has m characters, and the second string has n characters. We will only need at most m-n+1 times of loops. The reason is that if the first character has less then n remaining characters, and still cannot match the second string, we will know that the first string will not contain the second string. Therefore, we can use an additional pointer (walker), which serves as a counter. Let the walker point to the n-th position of the first string, advancing it through the loop, when it points to '\0', the loop ends. Therefore, we save the time by n steps (The length of the second string). How to make walker advance to n steps further first? Using two pointers! Make another pointer point to the second string, let them walking together. When the second pointer reaches '\0', i.e., after n steps, the first pointer will reach n steps after the beginning of the first string.

C++语言: strStr2

01 char *strStr(char *haystack, char *needle) {
02     if(*needle=='\0')
03         return haystack;
04     if(*haystack=='\0')
05         return NULL;
06     //two pointers, let step point to needle and walker to haystack
07     //advance step to the end of needle, then walker will advance n steps
08     char *step=needle;
09     char *walker=haystack;
10     while(*step!='\0')
11     {
12         step++;
13         walker++;
14     }
15     //back one step
16     walker--;      
17     char *start=haystack;
18     char *p;
19   
20     //using walker to control the loop times
21     while(*walker!='\0')
22     {
23         p=start;
24         char *q=needle;
25         while(*p!='\0' && *q!='\0' && *p==*q)
26         {
27             p++;
28             q++;
29         }
30         if(*q=='\0')
31         {
32             return start;
33         }
34         start++;
35         walker++;
36     }      
37     return NULL;
38 }

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution: using "divide and conquer" approach. Find the middle node of the linked list, then split around it to two lists, the left part and the right part. Set the middle node as the root, apply the algorithm recursively on the left list and the right list, set the results of them as the left child and the right child, respectively.

Java语言: SortedListToBST

01 public TreeNode sortedListToBST(ListNode head) {
02         //two base cases
03         if(head==null)
04             return null;
05         if(head.next==null)
06             return new TreeNode(head.val);
07     
08         //partition the list from the middle, use two pointers
09         //the slow pointer will be the prev of the middle node        
10           ListNode fast=head.next.next;
11         ListNode slow=head;
12         while(fast!=null && fast.next!=null)
13         {
14             fast=fast.next.next;
15             slow=slow.next;
16         }    
17         //find the middle node
18         ListNode parent=slow.next;
19         slow.next=null;
20     
21         //partition the list into left and right
22         ListNode left=head;
23         ListNode right=parent.next;
24         parent.next=null;
25     
26         //make the middle node as the root, then apply the function
27         //to the left part and the right part recursively
28         TreeNode root=new TreeNode(parent.val);                                    
29         root.left=sortedListToBST(left);          
30         root.right=sortedListToBST(right);
31         return root;
32     }
33 }

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.

Solution: use two hash tables to map a number to its longest sequence starting and ending at this number. Update the entries when you find numbers which are one more or one less than the current number in the table. Update the length of the interval as max.

Java语言: Longest Consecutive Sequence

01 public int longestConsecutive(int[] num) {
02     if(num.length<=1)
03         return num.length;
04     int max=1;
05     //Maps this number to the sequence start by this value;
06     Hashtable<Integer,Integer> start=new Hashtable<Integer,Integer>();
07     //Maps this number to the sequence end by this value;
08     Hashtable<Integer,Integer> end=new Hashtable<Integer,Integer>();
09     for(int i=0;i<num.length;i++)
10     {
11         //skip the number that has already seen
12         if(start.containsKey(num[i]))
13             continue;  
14       
15         start.put(num[i],1);
16         end.put(num[i],1);
17 
18         int lowerBound=num[i];          
19         int upperBound=num[i];
20       
21         //check the interval ending by its prev number
22         //get the lower bound that can be reached from the current  number
23         if(end.containsKey(num[i]-1))
24         {
25             lowerBound=num[i]-1-end.get(num[i]-1)+1;
26           
27         }
28         //check the interval starting from its next number
29         //get the upper bound that can be reached from the current number
30         if(start.containsKey(num[i]+1))
31         {
32             upperBound=num[i]+1+start.get(num[i]+1)-1;
33           
34         }
35         //update the interval
36         int range=upperBound-lowerBound+1;          
37         start.put(lowerBound, range);
38         end.put(upperBound, range);
39       
40         if(range>max)
41             max=range;          
42     }
43     return max;
44 }