[LeetCode] WildCard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

 解题思路：
1. 最开始想到的就是递归，但通不过大数据。
2. 后来又想到用数组，类似edit distance的dp。 如果 p(j) == '*', 则match[i][j] = match[i][j-1] || match[i-1][j]. 当p(j) == '?' or p(j) = s(i) 则，match[i][j] = match[i-1][j-1]. 但这样会需要很大的额外空间并且又多了很多不必要的计算。
3. 就是将解法1递归添加一个stack来存储 ＊和当前s的位置。但是同样通不过大数据，所以我们要进行进一步分析，进行剪枝优化
    3.1 首先想到的就是当多个*连续出现时，它等同于一个*
    3.2 每次回溯时，我们仅需要回溯到最近的一个*的相关位置，对之前出现的*, 我们可以舍弃.
   比如，s="accbcbccx", p="a*b*d",  "a*b" 可以与"accb" 或者 "accbcb" 匹配，当我们发现"cbccx"不能与"*d"匹配时，我们也不回溯到 "accbcb" 然后 匹配 "ccx" 与"*b"
因为第二个*可以匹配任何的字符。

Java Code:

 public boolean isMatch(String s, String p) {
        int s0 = 0;
        int p0 = 0;
        int pre_p = -1, pre_s = -1;
       
       while(s0 < s.length()){
           if(s0 < s.length() && p0 < p.length() && (s.charAt(s0) == p.charAt(p0) || p.charAt(p0) == '?')){
               s0++;
               p0++;
           }else if(p0 < p.length() && p.charAt(p0) == '*'){
               while(p0 < p.length() && p.charAt(p0) == '*') p0++;
               if(p0 == p.length()) return true;
               
               pre_p = p0;
               pre_s = s0;
           }else if(pre_p > -1){
               pre_s++;
               s0 = pre_s;
               p0 = pre_p;
           }else{
               return false;
           }    
       }
       
       while(p0 < p.length() && p.charAt(p0) == '*') p0++;
       
      return p0 == p.length();
    }

[LeetCode] N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
] 

解题思路：

1.与N-Queens 2的思路一致，不过此题需要额外多的变量来记录所有的解。 

Java Code:

 public List solveNQueens(int n) {
        List res = new ArrayList();
        int[] solution = new int[n];
    
        String[] curr = new String[n];
        Nqueen1(1, solution, curr, res);
        return res;
    }
    
    public void Nqueen1(int level, int[] solution, String[] curr, List res){
        
        if(level == solution.length + 1){
            res.add(Arrays.copyOf(curr, level-1));
            return;
        }
        
        for(int i = 1; i <= solution.length; i++){
            int slop0 = Math.abs(i - level);
            
                int j = 0; 
                while(j < level && solution[j] != i && Math.abs(j + 1- level) != Math.abs(solution[j] - i)){
                    j++;
                }
                
                if(j == level){
                    String tmp = "";
                    
                    for(int t = 1; t <= solution.length; t++){
                        if(t==i) tmp += "Q";
                        else tmp += ".";
                    }
                    
                   
                    solution[level-1] = i;
                    curr[level-1] = tmp;
                    Nqueen1(level + 1, solution, curr, res);
                    solution[level - 1] = 0;
                    curr[level - 1] = ""; 
                }
         }
    }

[LeetCode] Letters 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.

Java code

 public List letterCombinations(String digits) {
      String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        List prevList = new ArrayList();
        prevList.add("");
        
        for(int i = 0; i < digits.length(); i++){
            int digit = digits.charAt(i) - '0';
            List currList = new ArrayList();
            
            for(int j = 0; j < prevList.size(); j++){
                for(int t = 0; t < letters[digit].length(); t++){
                    currList.add(prevList.get(j)+letters[digit].substring(t, t+1));
                }
            }

            prevList.clear();
            prevList.addAll(currList);
        }
        
        return prevList;
     }

[LeetCode] Interleaving String

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.

解题思路：

DP， 和edit distance有点类似

    public boolean isInterleave(String s1, String s2, String s3) {
           int len1 = s1.length();
           int len2 = s2.length();
           
           if(s3.length() != len1 + len2) return false;
           
           boolean[][] match = new boolean[len1+1][len2+1];
           
           for(int i = 0; i <= len1; i++){
               for(int j = 0; j <= len2; j++){
                   if(i == 0 && j == 0){
                       match[i][j] = true;
                   }else{
                       if(j > 0 && s3.charAt(i+j-1) == s2.charAt(j-1)) match[i][j] = match[i][j] || match[i][j-1];
                       if(i > 0 && s3.charAt(i+j-1) == s1.charAt(i-1)) match[i][j] = match[i][j] || match[i-1][j];
                   }
               }
           }
           
           return match[len1][len2];
    }

[LeetCode] Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

解题思路：
        1. 对于ratings[i], ratings[i]的数目的大小，取决于ratings[i-1], ratings[i+1]和ratings[i]的大小对比。我们可以简化为，ratings[i-1] vs ratings[i] 或者ratings[i+1] vs ratings[i].
        从左到右扫描数组，candies[i] = candies[i-1] + 1 if ratisngs[i] > ratings[i-1]
          然后第二遍，从右到左，candies[i-1] = candies[i] + 1 if ratings[i-1] > ratisngs[i]
          第二遍，要注意在ratings[i-1] > ratings[i] and candies[i-1] > candies[i], 就不需要更改了candies了。

 
public int candy(int[] ratings) {
        int n = ratings.length;
        if(n == 0) return 0;
        
       int[] candies = new int[n];
       int total = 0;
       candies[0] = 1;
       
       
       for(int i = 1; i < ratings.length; i++){
           if(ratings[i] > ratings[i-1]){
               candies[i] = candies[i-1] + 1;
           }else{
               candies[i] = 1;
           }
       }
       
       total = candies[n - 1];
       
       for(int i = ratings.length - 1; i > 0 ; i--){
           if(ratings[i] < ratings[i-1] && candies[i] >= candies[i-1]){
               candies[i-1] = candies[i] + 1;
           }
               total += candies[i-1];
       }
       
       return total;
           
    }

[LeetCode] Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0 
01 - 1 
11 - 3
10 - 2

解题思路：
F（n） = F(n-1) + (F(n-1) in reverse order) + 1<<(n-1)

n个数的greycode等于 n-1的greycode再加上把greycode反序各自在第1位加个1

 public List grayCode(int n) {
          List res = new ArrayList();
         res.add(0);
         
         for(int i = 1; i <= n; i++){
             int j = res.size();
             int k = 1<<(i-1);
             
             while(j > 0){
                 res.add(res.get(j-1) + k);
                 j--;
             }
         }
         
       return res;
    }