Valid Word Abbreviation
链接：
注意第一个数字是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; Minimum Unique Word Abbreviation
题目链接：
又是一道backtracking的题。看了这个博客的解法：
现在是穷举可能的结果，注意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最后添上。明天研究性下怎么写时间复杂度的。
