Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

If you are interested in a more advanced algorithm, KMP algorithm, look this. This post will implement this problem using a hash function. It is based on the rolling hash method. Basically, we calculate a hash function for the pattern string, or the needle, and compare it with the text string, or the haystack. The hash function is calculated as the following way:

The constant is chosen as 29 in this case. When comparing with the haystack, we remove the first part of the hash function and add the part for the new character. It's like a sliding window. 

public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) 
            return -1;
        if (haystack.length() == 0)
         return needle.length() == 0 ? 0 : -1;
        if (needle.length() == 0)
            return 0;
        if (haystack.length() < needle.length())
         return -1;
        int base = 29;
        int n = needle.length();
        long tmpBase = 1;
        long needleHash = 0;
        
        for (int i = n - 1; i >= 0; i--) {
         needleHash += (long)needle.charAt(i) * tmpBase;
            tmpBase *= base;
        }
        tmpBase = 1;
        long haystackHash = 0;
        for (int i = n - 1; i >= 0; i--) {
            haystackHash += (long)haystack.charAt(i) * tmpBase;
            tmpBase *= base;
        }
        if (haystackHash == needleHash)
            return 0;
        tmpBase /= base;
        for (int i = n; i < haystack.length(); i++) {
            haystackHash = (haystackHash - (long)haystack.charAt(i - n) * tmpBase) * base + (long)haystack.charAt(i);
            if (haystackHash == needleHash)
                return i - n + 1;
        }
        return -1;
    }

Update: 2015 - 01 - 19
As usual, my curiosity drove me to do the following performance test. It looks like KMP algorithm does hit the lower bound of the complexity:

P.S.: The test strings, if you are interested, are:

String haystack = "mississippimississippimississipippimissisippimissisippimissispimississippimississippimississippimississippimississippiabcabdabc"

String needle = "abcabdabc"

P.P.S: The KMP code:

public int strStr(String haystack, String needle) {
        if (needle == null || needle.length() == 0)
            return 0;
        if (haystack == null || haystack.length() == 0)
            return -1;
        if (haystack.length() < needle.length())
            return -1;
        int n = needle.length();
        int h = haystack.length();
        int[] PMT = getPMT(needle);
        int index_h = 0;
        int index_n = 0;
        while (index_h < h) {
            while(index_n >= 0 && haystack.charAt(index_h) != needle.charAt(index_n))
                index_n = PMT[index_n];
            index_h++;
            index_n++;
            if (index_n == n)
                return index_h - n;
        }
        return -1;
    }
    
    private int[] getPMT(String needle) {
        int[] PMT = new int[needle.length() + 1];
        PMT[0] = -1;
        PMT[1] = 0;
        for (int i = 2; i <= needle.length(); i++) {
            PMT[i] = (needle.charAt(i - 1) == needle.charAt(PMT[i - 1])) ? PMT[i - 1] + 1 : 0;
        }
        return PMT;
    }

Knuth - Morris - Pratt Algorithm: Let's give it a fancy name, pattern match

The initiative of studying this algorithm is because of this problem from LeetCode:

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

It is an easy level problem, yet I spend my whole night figuring out this algorithm. And yes, I missed the Golden Globe (Congratulations to Eddie Redmayne, who portrayed one of my favorite physicists Stephen Hawking).

This algorithm is indeed a very interesting one. At first glance, it is very hard to understand, and require O(m) extra space, but if you really take some effort and try to understand it, you will realize how neat it can make the whole method.

Partial Match Table
Ok, start from Partial Match Table / Failure Function (PMT).  There are lots of resources to explain it, some of them are very fancy and complicated, I put the Wikipedia link here if you want some official explanation. Mine will be simpler. The partial match table matches the longest prefix and suffix that are equal of all substrings in a string. The prefix and suffix do not include the substring.
For example, consider string ="abcabdabc" will form a PMT as shown in the following table.

For an empty substring, the length is not defined, so we choose -1. Another reason to choose -1 is that when we use this table later in the pattern match, it will be easier for index incrementation. For a substring with length equals to 1, there is no prefix or suffix that doesn't include the whole substring, so the length = 0. For substring with length equal to 2 and 3, no equal prefix and suffix is found, so lengths still equal to 0. And we move on....

So how to calculate the PMT? Take a look at the table again. For "ab", since the length of equal prefix  & suffix = 0 for the previous substring "a", we compare the first character and the last character, since they are not equal, the length is still 0. Same for "abc", now it comes to "abca", since the the first and last character are equal, the length is 1. Or it is 0 + 1. Then it comes to "abcab", we already know from the last substring that the first character equals the last character (of the last substring), now we add one more character, we compare the second character with the last character (of this substring), the length is 2, or 1 + 1, You see the trend here? Every time, we compare the next character after the longest prefix (that equals to the suffix) with the last character, if the longest prefix = 0, we compare the first character with the last one, if the longest prefix = 1, we compare the second character, which has the index 1, with the last character. However, if the characters compared are not equal, the longest prefix = 0, i.e., :

PMT[i] = (ptrn.charAt(i - 1) == ptrn.charAt(PMT[i - 1])) ? (PMT[i - 1] + 1) : 0;

Yeah, as you know, it's DP.

What is the table used for? 

Considering a text string = "abcabcabdabcabcabdabdabc" (I am making it larger to look clearer), how to find the previous pattern string we showed above? You can say we compare each character in the pattern with the text string, if any character doesn't match, we slide the pattern string down to the next character in the text string that matches the first character in the pattern string. Yes, we can do that way, but it will take O(mn) time where m is the length of the pattern string and n is the length of the text string. So, can we do better? 

Look at the above figure, now we are at index 5 and the characters don't match. Since we already know that "abcab" has the longest prefix and suffix = 2, that means"ab" matches with "ab", now if we compare the character at index 5 in the text string with the character at index 2 (from the PMT table), they match, so next time we start from the characters at index 6 in the text string and index 3 at pattern string. If they don't match, say the following string, then from the table, the longest prefix of substring "ab" is 0, so unfortunately, we need to start over.

Using this algorithm allows us to trim off lots of unnecessary comparisons, the complexity is O(m + n) compared to the brutal force implementation. However, when the length of the string increases and mismatch increases, the complexity also increases.

public class KMP {
 private int[] getPMT(String ptrn) {
  int ptrnLen = ptrn.length();
  //partial match table
  int[] PMT = new int[ptrnLen + 1];
  PMT[0] = -1;
  PMT[1] = 0;
  for (int i = 2; i <= ptrnLen; i++) {
   PMT[i] = (ptrn.charAt(i - 1) == ptrn.charAt(PMT[i - 1])) ? (PMT[i - 1] + 1) : 0;
   System.out.println(i + ": " + PMT[i]);
  }
  return PMT;
  
     
    
 }
 public List searchSubString(String text, String ptrn) {
  if (text == null || ptrn == null)
   throw new NullPointerException("Null String(s)!");
  List rst = new ArrayList ();
  if (ptrn.length() == 0) {
   rst.add(0);
   return rst;
  }
  if (text.length() == 0 || text.length() < ptrn.length()) {
    return rst;
  }
  
  int indexT = 0;
  int indexP = 0;
  int ptrnLen = ptrn.length();
  int txtLen = text.length();
  int[] PMT = getPMT(ptrn);
  while (indexT < txtLen) {
   while (indexP >= 0 && text.charAt(indexT) != ptrn.charAt(indexP)) {
    indexP = PMT[indexP];
   }
   indexP++;
   indexT++;
   if (indexP == ptrnLen) {
    rst.add(indexT - ptrnLen);
    indexP = PMT[indexP];
   }
  }
  return rst;
 }

Source code can be found here: https://github.com/shirleyyoung0812/Knuth-Morris-Pratt-Algorithm.git

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

In order to check if a number is a palindrome, we need to keep checking the first and last digit of the number. To get the last digit is trivial, i.e., x % 10, but how to get the first digit?

Thinking about how you will do to trim the last digit from a number? Divide the number by 10, right? So this time, we do it in the reverse way: multiply a number by 10: Start from 1, if x / divisor >= 10, it means we haven't reached the first digit, we need to keep multiply the divisor by 10, until we reach the first the digit. Note I did it this way at first:

int divisor = 1;
        while (divisor < x)
            divisor *= 10;
        divisor /= 10;

The divisor will overflow for large x, so no, this won't work.

The rest part is easy, keep checking the first and last digit and divide the divisor by 100 (each time we trim two digits).

public boolean isPalindrome(int x) {
        if (x < 0)
            return false;
        if (x > 0 && x < 10)
            return true;
        int divisor = 1;
        while (divisor < x)
            divisor *= 10;
        divisor /= 10;
        while (x > 0) {
            int right = x % 10;
            int left = x / divisor;
            if (left != right)
                return false;
            x -= (x / divisor * divisor);
            x /= 10;
            divisor /= 100;
        }
        return true;
    }

Pascal's Triangle I & II

I write about this problem only to clarify how to use ArrayList correctly. ArrayList has a constructor:

public ArrayList(int initialCapacity)

Constructs an empty list with the specified initial capacity.

Parameters:

initialCapacity - the initial capacity of the list

Throws:

IllegalArgumentException - if the specified initial capacity is negative

I thought at first that it can create a list with size of "initialCapacity", apparently that is not the case. It still creates an empty array. However, the "initialCapacity" is the initial capacity of the backing array of the list:

 public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

So the correct way is to create a list and add as many elements as the desired size, then use the set() method to modify the list.

Back to these two problem. The current level of the Pascal's Triangle can be generated from the previous level. So start with the first level, which is 1, we can generate the desired number of rows.

Pascal's Triangle I

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

public List> generate(int numRows) {
        List> rst = new ArrayList> ();
        if (numRows <= 0)
            return rst;
        for (int i = 1; i <= numRows; i++) {
            List curr = new ArrayList ();
            for (int j = 0; j < i; j++) 
                curr.add(-1);
            curr.set(0, 1);
            curr.set(i - 1, 1);
            if (i == 1)
                rst.add(curr);
            else {
                for (int j = 1; j < i - 1; j++) {
                    int n = rst.get(rst.size() - 1).get(j - 1) + rst.get(rst.size() - 1).get(j);
                    curr.set(j, n);
                }
                rst.add(curr);
            }
        }
        return rst;
    }

Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

public List getRow(int rowIndex) {
        List rst = new ArrayList ();
        if (rowIndex < 0)
            return rst;
        rst.add(1);
        if (rowIndex == 0)
            return rst;
        List prev = new ArrayList(rst);
        for (int i = 1; i <= rowIndex; i++) {
            rst = new ArrayList();
            for (int j = 0; j < i + 1; j++) {
                rst.add(-1);
            }
            rst.set(0, 1);
            rst.set(i, 1);
            for (int j = 1; j < i; j++) {
                int n = prev.get(j - 1) + prev.get(j);
                rst.set(j, n);
            }
            prev = new ArrayList(rst);
        } 
        return rst;
    }

Excel Sheet Column Title / Excel Sheet Column Number

These two problems are just testing you how to convert from base X (in this case, X = 26) to base 10. The first problem requires us to convert from base 10 to base 26 and the second one asks to the reverse.

Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

public String convertToTitle(int n) {
        if (n <= 0)
            return "";
        String rst = "";
        while (n > 0) {
            int tmp = n % 26;
            n = n / 26;
            if (tmp == 0) {
                rst = "Z" + rst;
                n -= 1;
            }
            else {
               char cha = (char)(tmp + 'A' - 1);
               rst = String.valueOf(cha) + rst;
            }
            
        }
        return rst;
    }

Excel Sheet Column Number

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

public int titleToNumber(String s) {
        if (s == null)
            throw new NullPointerException("Null String!");
        if (s.length() == 0)
            return 0;
        int l = s.length();
        int sum = 0;
        for (int i = 0; i < l; i++) {
            sum += Math.pow(26, l - 1 - i) *(s.charAt(i) - 'A' + 1);
        }
        return sum;
    }

Container With Most Water

At first I was thinking about using the same strategy as the one we used in Largest Rectangle in Histogram, or Trapping Rain Water. But none of them worked. The difference between this problem and Largest Rectangle in Histogram is that in the latter, the rectangles should be adjacent to each other (see the following figure, the largest rectangle should be among 1 to 5).

Largest Rectangle in Histogram

In this problem, we only deal with lines. So the containers can be any rectangles formed by elements from 0 to 6 . For any element i in the array, the largest element will the the farthest element j from i that has num[j] > num[i].

Container with Most Water

public int maxArea(int[] height) {
        if (height == null)
            throw new NullPointerException("Null array!");
        if (height.length < 2)
            return 0;
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, h * (right - left));
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return maxArea;
    }

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Backtracking problem. Use a map <Integer, char[] > (or list) to store the mapping between numbers and letters. Starts from 0, every time we add one letter to the StringBuilder, its length will increment by 1. So in each recursion, we start the loop at the length of the string builder, which points to the next number in string digits whose mapping is to be added.

public List letterCombinations(String digits) {
        if (digits == null)
            throw new NullPointerException("Null string!");
        List rst = new ArrayList ();
        Map map = new HashMap();
        map.put('0', new char[] {});
        map.put('1', new char[] {});
        map.put('2', new char[] { 'a', 'b', 'c' });
        map.put('3', new char[] { 'd', 'e', 'f' });
        map.put('4', new char[] { 'g', 'h', 'i' });
        map.put('5', new char[] { 'j', 'k', 'l' });
        map.put('6', new char[] { 'm', 'n', 'o' });
        map.put('7', new char[] { 'p', 'q', 'r', 's' });
        map.put('8', new char[] { 't', 'u', 'v'});
        map.put('9', new char[] { 'w', 'x', 'y', 'z' });
        getLetter(digits, map, rst, new StringBuilder ());
        return rst;
    }
    private void getLetter(String digits, Map map, List rst, StringBuilder sb) {
        if (sb.length() == digits.length()) {
            rst.add(sb.toString());
            return;
        }
        for (char c : map.get(digits.charAt(sb.length()))) {
            sb.append(c);
            getLetter(digits, map, rst, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }