摘要：鏈接注意第一個數字是的情況，這種也是不合法的。還有一個注意的就是要想和有相同的縮寫，長度必須和它相同，所以只保留長度相同的。注意剪枝，當前長度已經超過就不需要繼續了。二進制的做法是這樣的，先對字典里面的單詞進行處理。

鏈接：https://leetcode.com/problems...

注意第一個數字是0的情況，["a", "01"]這種也是不合法的。

public class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        /* while loop, i for word, j for abbr
         * if it is number: count the number
         * i += number
         * else: compare word.charAt(i) == abbr.charAt(j)
         * end: i < len(word) && j < len(abbr)
         * return i == len(word) && j == len(abbr)
         */
         int i = 0, j = 0;
         while(i < word.length() && j < abbr.length()) {
             // character
             if(abbr.charAt(j) > "9" || abbr.charAt(j) <= "0") {
                 // characters not same
                 if(word.charAt(i) != abbr.charAt(j)) return false;
                 i++;  j++;
             }
             // count number
             else {
                 int count = 0;
                 while(j < abbr.length() && Character.isDigit(abbr.charAt(j))) {
                     count = 10 * count + (abbr.charAt(j) - "0");
                     j++;
                 }
                 i += count;
             }
         }
         
         return i == word.length() && j == abbr.length();
    }
}

        // if number: 
        // if character: check the same
        int i = 0;
        int m = word.length(), n = abbr.length();
        int count = 0;
        for(int j = 0; j < abbr.length(); j++) {
            char c = abbr.charAt(j);
            // number
            if(c >= "0" && c <= "9") {
                if(count == 0 && c == "0") return false;
                count = count * 10 + (c - "0");
            }
            // digit
            else {
                i += count;
                if(i >= word.length() || word.charAt(i) != c) return false;
                count = 0;
                i++;
            }
        }
        return i + count == m;

題目鏈接：https://leetcode.com/problems...

又是一道backtracking的題。看了這個博客的解法：
http://bookshadow.com/weblog/...

現在是窮舉可能的結果，注意prune，然后check是否有和dict相同的。還有一個注意的就是要想和target有相同的縮寫，長度必須和它相同，所以dict只保留長度相同的。注意剪枝，當前長度已經超過globalMin就不需要繼續了。

public class Solution {
    public String minAbbreviation(String target, String[] dictionary) {
        // only keep the words has the same length
        int len = target.length();
        for(String s : dictionary) {
            if(s.length() == len) dict.add(s);
        }
        // no word has the same length as target
        if(dict.isEmpty()) return String.valueOf(target.length());
        globalMin = len;
        global = target;
        dfs(target, 0, 0, "");
        return global;
    }
    Set dict = new HashSet();
    int globalMin;
    String global;
    private void dfs(String target, int index, int len, String abbr) {
        // pruning
        if(len >= globalMin) return;
        // base case
        if(index == target.length()) {
            for(String word : dict) {
                if(validWordAbbreviation(word, abbr)) return;
            }
            globalMin = len;
            global = abbr;
            return;
        }
        // 2 subproblems:
        // 1. target[i] = char 
        // 2. target[i] = num
        dfs(target, index + 1, len + 1, abbr + target.charAt(index));
        int abbr_len = abbr.length();
        if(index == 0 || !Character.isDigit(abbr.charAt(abbr_len - 1))) {
            dfs(target, index + 1, len + 1, abbr + 1);
        }
        else {
            int num = 1 + (abbr.charAt(abbr_len - 1) - "0");
            dfs(target, index + 1, len, abbr.substring(0, abbr_len-1) + num);
        }
    }
    
    private boolean validWordAbbreviation(String word, String abbr) {
        // if number: 
        // if character: check the same
        int i = 0;
        int m = word.length(), n = abbr.length();
        int count = 0;
        for(int j = 0; j < abbr.length(); j++) {
            char c = abbr.charAt(j);
            // number
            if(c >= "0" && c <= "9") {
                if(count == 0 && c == "0") return false;
                count = count * 10 + (c - "0");
            }
            // digit
            else {
                i += count;
                if(i >= word.length() || word.charAt(i) != c) return false;
                count = 0;
                i++;
            }
        }
        return i + count == m;
    }
}

還有bit的方法，感覺好厲害！！完全沒想出來。
二進制的做法是這樣的，先對字典里面的單詞進行處理。一個char一個char處理，如果該char和target對應位置上的一樣，則記為1，否則記為0，這樣處理完之后就知道哪些位置上的字母可以換成數字。對target進行縮寫的時候，保留字母的記為1，換成數字的記為0，這樣查target的abbr是否是word的縮寫時，只需要把兩者相與看是否和abbr相同即可。
我還是沒搞懂這個到底是怎么想出來的，明天再看看。

public class Solution {
    public String minAbbreviation(String target, String[] dictionary) {
        len = target.length();
        globalMin = target.length()+1;
        global = 0;
        getBitDict(target, dictionary);
        // edge case: target in dict, no word with same len
        if(globalMin == 0) return target;
        if(dict.size() == 0) return String.valueOf(len);
        // backtracking
        dfs(0, 0, 0);
        return bitToString(target);
    }
    
    List dict = new ArrayList();
    int globalMin;
    int global;
    int len;
    private void dfs(int index, int curLen, int abbr) {
        // prune
        if(curLen >= globalMin) return;
        // base case
        if(index == len) {
            for(int word : dict) {
                if((word & abbr) == abbr) return;
            }
            globalMin = curLen;
            global = abbr;
            return;
        }
        // 1. character
        dfs(index + 1, curLen + 1, (abbr << 1) + 1);
        // 2. number
        if(index == 0 || (abbr%2) == 1) dfs(index + 1, curLen + 1, (abbr << 1));
        else dfs(index + 1, curLen, (abbr << 1));
    }

    
    private void getBitDict(String target, String[] dictionary) {
        // bit: 1. s[i] == target[i] => 1
        //      2. s[i] != target[i] => 0
        int len = target.length();
        for(String s : dictionary) {
            if(s.length() == len) {
                // edge case
                if(s.equals(target)) {
                    globalMin = 0;
                    return;
                }
                int bitString = 0;
                for(int i = 0; i < len; i++) {
                    bitString = bitString << 1;
                    if(target.charAt(i) == s.charAt(i)) bitString += 1;
                }
                dict.add(bitString);
            }
        }
    }
    
    private String bitToString(String target) {
        String result = "";
        int count = 0;
        for(int i = 0; i < len; i++) {
            if(((global >> len - i - 1) & 1) == 1) {
                if(count != 0) result += count;
                count = 0;
                result += target.charAt(i);
            }
            else count++;
        }
        if(count != 0) result += count;
        return result;
    }
}

練習白板第一天，板子買小了。思路寫的也不整齊，擦了好幾次，大概寫了30分鐘，還需要多多練習額。。dfs的題，下次寫的時候，還是按照start -> arguments&return type -> base case -> subproblem的順序來，pruning最后添上。明天研究性下怎么寫時間復雜度的。