Implement strStr()

Implement strStr().

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

KMP和RK会在以后补上。暴力方法：

public class Solution {
    //Time: O(m*n)  Space: O(1)
    public String strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return null;
        }
        if (needle.length() == 0) {
            return haystack;
        }
        
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            int length = 0;
            for (int j = i; j < needle.length() + i; j++) {
                if (haystack.charAt(j) == needle.charAt(j - i)) {
                    length++;
                } else {
                    break;
                }
                if (length == needle.length()) {
                    return haystack.substring(i);
                }
            }
        }
        return null;
    }
}

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

用左右两个指针，右指针往右移同时把char加进hashset里面，当hashset出现重复时，计算当前长度，移动左指针，一直到左指针指向重复的元素，把经过的元素移除hashset。重复以上过程。

public class Solution {
    //Time: O(n)  Space: O(n)
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) {
            return s.length();
        }
        
        HashSet<Character> set = new HashSet<Character>();
        int left = 0;
        int i = 0;
        int max = 0;
        for (; i < s.length(); i++) {
            if (!set.contains(s.charAt(i))) {
                set.add(s.charAt(i));
            } else {
                max = Math.max(max, i - left);
                while (left < i && s.charAt(left) != s.charAt(i)) {
                    set.remove(s.charAt(left));
                    left++;
                }
                left++;
            }
        }
        max = Math.max(max, i - left);
        return max;
    }
}

Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Anagrams 指对于不同string，他们不同char的出现次数一样。我们可以用一个26size的array来记录每个string各种char出现的次数，用它来计算对应每个string的hash value，如果是anagrams，value也会相同。把结果放进HashMap，对于每个value，如果对应的string个数大于1，就加进结果里。

public class Solution {
    //Time: O(n * m) m is average length of each string
    public ArrayList<String> anagrams(String[] strs) {
        ArrayList<String> res = new ArrayList<String>();
        if (strs == null || strs.length == 0) {
            return res;
        }
        
        HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
        for (int i = 0; i < strs.length; i++) {
            int[] count = new int[26];
            String s = strs[i];
            for (int j = 0; j < s.length(); j++) {
                count[s.charAt(j) - 'a']++;
            }
            int val = getValue(count);
            if (!map.containsKey(val)) {
                ArrayList<String> tmp = new ArrayList<String>();
                tmp.add(s);
                map.put(val, tmp);
            } else {
                ArrayList<String> tmp = map.get(val);
                tmp.add(s);
                map.put(val, tmp);
            }
        }
        
        for (int i : map.keySet()) {
            if (map.get(i).size() > 1) {
                res.addAll(map.get(i));
            }
        }
        return res;
    }
    
    private int getValue(int[] count) {
        int val = 0;
        for (int i = 0; i < count.length; i++) {
            val = val * 31 + count[i];
        }
        return val;
    }
}

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.

用一个二维数组进行DP，map[i][j] 表示T在长度前j位在S长度前i位合法的个数。当第i位和第j位char不同，我们只能考虑删掉第i位，相同时还能考虑保留第i为。

public class Solution {
    //Time: O(m * n)  Space: O(m * n)
    public int numDistinct(String S, String T) {
        if (S.length() < T.length()) {
            return 0;
        }
        
        int m = S.length();
        int n = T.length();
        int[][] map = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            map[i][0] = 1;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                map[i][j] += map[i - 1][j];
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    map[i][j] += map[i - 1][j - 1];
                }
            }
        }
        return map[m][n];
    }
}

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

用一个二维数组，map[i][j]  代表从word1(0,i)变化到word2(0,j)需要的次数。

public class Solution {
    //Time: O(m*n)  Space: O(m*n)
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) {
            return word2.length();
        }
        
        if (word2.length() == 0) {
            return word1.length();
        }
        
        int m = word1.length() + 1;
        int n = word2.length() + 1;
        int[][] map = new int[m][n];
        for (int i = 1; i < m; i++) {
            map[i][0] = i;
        }
        for (int i = 1; i < n; i++) {
            map[0][i] = i;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    map[i][j] = map[i - 1][j - 1];
                } else {
                    int delete = map[i - 1][j] + 1;
                    int insert = map[i][j - 1] + 1;
                    int replace = map[i - 1][j - 1] + 1;
                    map[i][j] = Math.min(delete, Math.min(insert, replace));
                }
            }
        }
        return map[m - 1][n - 1];
    }
}

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [

    ["aa","b"],

    ["a","a","b"]

  ]

DFS，时间分析，一个有n-1的地方可以断开，所以有断和不断两种情况，所有情况就是2^n。 

public class Solution {
    //Time: O(2^n)
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        ArrayList<String> tmp = new ArrayList<String>();
        help(res, tmp, s, 0);
        return res;
    }
    
    private void help(ArrayList<ArrayList<String>> res, ArrayList<String> tmp, 
                      String s, int index) {
        if (index == s.length()) {
            res.add(new ArrayList<String>(tmp));
            return;
        }
        
        for (int i = index + 1; i <= s.length(); i++) {
            String cur = s.substring(index, i);
            if (valid(cur)) {
                tmp.add(cur);
                help(res, tmp, s, i);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
    
    private boolean valid(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

public class Solution {
    //Time: O(n)
    public String addBinary(String a, String b) {
        if (a.length() == 0) {
            return b;
        }
        if (b.length() == 0) {
            return a;
        }
        
        StringBuilder res = new StringBuilder();
        int m = a.length() - 1;
        int n = b.length() - 1;
        int carry = 0;
        while (m >= 0 || n >= 0) {
            if (m >= 0) {
                carry += a.charAt(m) == '1' ? 1 : 0;
                m--;
            }
            if (n >= 0) {
                carry += b.charAt(n) == '1' ? 1 : 0;
                n--;
            }
            res.append(carry % 2);
            carry /= 2;
        }
        if (carry == 1) {
            res.append(1);
        }
        res.reverse();
        return res.toString();
    }
}

Letter Combinations of a Phone Number

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

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.

用一个HashMap存好对应关系，然后DFS。

public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        HashMap<Integer, char[]> map = new HashMap<Integer, char[]>();
        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'});
        combination(digits, map, res, 0, "");
        return res;
    }
    
    private void combination(String digits, HashMap<Integer, char[]> map,
                             ArrayList<String> res, int index, String s) {
        if (index == digits.length()) {
            res.add(s);
            return;
        }          
        
        char[] candidate = map.get(digits.charAt(index) - '0');
        for (int i = 0; i < candidate.length; i++) {
            combination(digits, map, res, index + 1, s + candidate[i]);
        }
    }
}

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

根据题目的意思进行递归操作，递归N次。有时候在整个循环结束时，记得检查下，最后一些case有没有加进结果里。

public class Solution {
    public String countAndSay(int n) {
        if (n < 1) {
            return "";
        }
        
        return countHelp("1", n - 1);
    }
    
    private String countHelp(String s, int num) {
        if (num == 0) {
            return s;
        }
        
        StringBuilder res = new StringBuilder();
        char cur = s.charAt(0);
        int count = 1;
        for (int i = 1; i < s.length(); i++) {
            if (cur == s.charAt(i)) {
                count++;
            } else {
                res.append(count);
                res.append(cur);
                cur = s.charAt(i);
                count = 1;
            }
        }
        res.append(count);
        res.append(cur);
        return countHelp(res.toString(), num - 1);
    }
}

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

比较直观，两两比较，更新prefix，当prefix已经为""时，可以直接结束。

public class Solution {
    //Time: O(n * average length of each String)
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            while (j < prefix.length() && j < strs[i].length()) {
                if (prefix.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
                j++;
            }
            prefix = prefix.substring(0, j);
            if (prefix == "") {
                return "";
            }
        }
        return prefix;
    }
}

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

用一个stack，如果是括号左边push，右边就和pop出来的比较是否为一对（检查stack是否已经为空）。最后检查遍历完后，stack是否为空。

public class Solution {
    //Time: O(n)
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        HashMap<Character, Character> map = new HashMap<Character, Character>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        Stack<Character> stack = new Stack<Character>();
        
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty() || map.get(stack.peek()) != s.charAt(i)) {
                    return false;
                }
                stack.pop();
            }
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }
}

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

首先找到第一不是空格的地方，然后找第二个。
如果能改变string，可以用trim预处理string，可以省去第一步。

public class Solution {
    //Time: O(n)
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int right = s.length() - 1;
        for (; right >= 0; right--) {
            if (s.charAt(right) != ' ') {
                break;
            }
        }
        if (right < 0) {
            return 0;
        }
        int left = right;
        for (; left >= 0; left--) {
            if (s.charAt(left) == ' ') {
                break;
            }
        }
        return right - left;
    }
}

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

判断string是否是Palindrome，此题只考虑数字字母，字母不用区分大小写，无视所有符号和空格。所以我们可以用左右两个指针边检测边压缩，一直到两个指针重合。

Character.isDigit(...) 和 Character.isLetter(...)这两个函数帮我们省去了很多麻烦。

public class Solution {
     //Time: O(n) Space: O(1)
     public boolean isPalindrome(String s) {
         if (s == null || s.length() <= 1) {
             return true;
         }
         
         s.trim();
         int left = 0;
         int right = s.length() - 1;
         while (left < right) {
             while (left < s.length() && !Character.isDigit(s.charAt(left)) && 
                    !Character.isLetter(s.charAt(left))) {
                 left++;           
             }
             if (left == s.length()) {
                 break;
             }
             while (right >= 0 && !Character.isDigit(s.charAt(right)) && 
                    !Character.isLetter(s.charAt(right))) {
                 right--;           
             }
             if (right < 0) {
                 break;
             }
             if (Math.abs(s.charAt(left) - s.charAt(right)) != 0 && 
                 Math.abs(s.charAt(left) - s.charAt(right)) != 'a' - 'A') {
                 return false;        
             }
             left++;
             right--;
         }
         return true;
     }
}