字符串压缩

288. Unique Word Abbreviation

题不难，但在是否unique的判断上要多想一想不同的情况。

public class ValidWordAbbr {
    Map<String, String> map;

    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String str : dictionary) {
            String key = getKey(str);

            // If there is more than one string belong to the same key
            // we set the value to "", make sure any string that has this key would be not unique

            // For example, door and deer, we have two strings belong to d2r, 
            // then door and deer would be not unique

            // If we have hello belongs to h3o, next time we check hello with hello as value
            // we know that hello would be unique
            if(map.containsKey(key)){
                if(!map.get(key).equals(str)){
                    map.put(key, "");
                }
            } else {
                map.put(key, str);
            }
        }
    }

    public boolean isUnique(String word) {
        return !map.containsKey(getKey(word)) || map.get(getKey(word)).equals(word);
    }

    private String getKey(String s) {
        if (s.length() <= 2) return s;
        return s.charAt(0) + Integer.toString(s.length() - 2) + s.charAt(s.length() - 1);
    }
}

320. Generalized Abbreviation

典型的搜索问题，DFS + backtracking，放到后面再写。

Check Word Abbreviation

G家面试题

public class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int i = 0;
        int j = 0;
        int number = 0;
        while (i < word.length() && j < abbr.length()) {
            if (Character.isDigit(abbr.charAt(j))) {
                number = number * 10 + abbr.charAt(j) - '0';
                if (number == 0) return false;
                j++;
            } else {
                i += number;
                if (i >= word.length() 
                    || word.charAt(i) != abbr.charAt(j)) return false;
                number = 0;
                i++;
                j++;
            }
        }
        i += number;
        return i == word.length() && j == abbr.length();
    }
}

527. Word Abbreviation / Word Abbreviation

又是G家面试题，Google的面试题特点就是实现麻烦，细节逻辑繁琐，比较考验代码功底，另外就是一般出原题较少，有时会出原题变种，不过leetcode的特点就是Google出一道新题，lc就收录一道。

我看这道题LC也挺坑爹的，非要给一个list返回一个list，想用数组还得换来换去的，然后在Java里面用HashMap有的地方也麻烦，这道题用Java比用C++要麻烦不少。

public class Solution {
    public List<String> wordsAbbreviation(List<String> dict) {
        List<String> res = new ArrayList<>();
        if (dict == null || dict.size() == 0) return res;

        int[] prefix = new int[dict.size()];
        String[] result = new String[dict.size()];

        for (int i = 0; i < dict.size(); ++i) {
            prefix[i] = 1;
            result[i] = getAbbr(dict.get(i), 1);
        }
        for (int i = 0; i < result.length; ++i) {
            while (true) {
                Set<Integer> set = new HashSet<>();
                for (int j = i + 1; j < result.length; ++j) {
                    if (result[j].equals(result[i])) set.add(j);
                }
                if (set.isEmpty()) break;
                set.add(i);
                for (int k : set) {
                    result[k] = getAbbr(dict.get(k), ++prefix[k]);
                }
            }
        }
        return Arrays.asList(result);
    }
    private String getAbbr(String s, int pre) {
        if (s.length() - pre <= 2) return s;
        return s.substring(0, pre) + Integer.toString(s.length() - 1 - pre) + s.charAt(s.length() - 1);
    }
}