Generalized Abbreviation

每次两个选择，cash out当前字符，注意判断count==0时，append “”字符串。count>0 append count；不cash当前字符，count++. 结尾时注意别漏了count。

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<String>();
        helper(word, 0, 0, "",result);
        return result;
    }

    public void helper(String word, int start, int count, String cur, List<String> result){
        if(start==word.length()){
            if(count>0)
                cur+=count;
            result.add(cur);
            return;
        }

        helper(word, start+1, count+1, cur, result);
        helper(word, start+1, 0, cur+ (count>0?count:"")+word.charAt(start), result);


    }
}

Minimum Unique Word Abbreviation

Word Abbreviation 升级版， 核心在于如果生成dictionary的所有abbreviation排列后比较会超时， 生成abbriaviation排列expensivie，是2toN。对于这类搜索一个单词在一个字典里时， 优先考虑用Trie。这道题最后就是Trie tree加数字的搜索， 注意判断边界条件。

跌跌撞撞总算AC。。。

public class Solution {

    class TrieNode{
        char c;
        HashMap<Character, TrieNode> map;
        public boolean isLeaf;
        TrieNode(){
            map = new HashMap<Character, TrieNode>();
        }
    }

    public void add(String s , TrieNode cur){
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(cur.map.containsKey(c)){
                cur = cur.map.get(c);
            }
            else{
                TrieNode tmp = new TrieNode();
                cur.map.put(c, tmp);
                cur = tmp;
            }
            if(i==s.length()-1){
                cur.isLeaf = true;;
            }
        }
    }

    public void generate(String target, List<String> abbr, int start, int count, String cur){
        if(start == target.length()){
            if(count!=0) cur+=count;
            abbr.add(cur);
            //System.out.println("generate: " + cur);
            return;
        }
        //don't add
        generate(target, abbr, start+1, count+1, cur);
        //add
        if(count!=0)
            cur+=count;
        cur+=target.charAt(start);
        generate(target, abbr, start+1, 0, cur);
    }

    public boolean search(String str, TrieNode cur, int count){
        //System.out.println(str + " " + cur.isLeaf + " " + count);
        if(count==0 && str.length()==0 && !cur.isLeaf) return false;
        if(count==0 && str.length()==0 && cur.isLeaf) return true;


        if(str.length()==1 && count==0){
            char c = str.charAt(0);
            if(!Character.isDigit(c)){
                if(cur.map.containsKey(c))
                    return cur.map.get(c).isLeaf;
                return false; 
            }
        }

        if(count!=0){
            for(Character key : cur.map.keySet()){
                if(search(str, cur.map.get(key), count-1))
                    return true;
            }
            return false;
        }
        int i=0;
        for(;i<str.length() && Character.isDigit(str.charAt(i));i++);
        String digits = str.substring(0, i);
        if(digits.length()>0){
            count = Integer.valueOf(digits);
            String remain = str.substring(i);
            return search(remain, cur, count);
        }
        else{
            char c = str.charAt(0);
            if(cur.map.containsKey(c)){
                return search(str.substring(1), cur.map.get(c), count);
            }
        }
        return false;
    }

    public String minAbbreviation(String target, String[] dictionary) {
        TrieNode root = new TrieNode();
        int maxL = 0;
        for(String s : dictionary){
            maxL = Math.max(maxL, s.length());
            add(s, root);
        }
        if(target.length()>maxL) return target.length()+"";
        List<String> abbr = new ArrayList<String>();
        int minLen = Integer.MAX_VALUE;
        String ans = "";
        generate(target, abbr, 0, 0, "");
        for(String str : abbr){
            //System.out.println("search: " + str);
            if(!search(str, root, 0)){
                if(str.length()<minLen){
                    ans = str;
                    minLen = str.length();
                }
            }

        }
        return ans;
    }
}

Word Abbreviation(Google, Snapchat)

开始把这个题想复杂了, "i4n1l"和"i4v1l"这种形式是不被允许的,开始的时候想了Trie, 怎么solve conflict, 还是要仔细分析题意.

这个题题意比较晦涩, 对任何两个字符串, 缩短后不能有歧义, 比如 "internal" 和"interval",可以转为"i6l"和"in5l", 然而这两个转回去都可以代表"internal"和"interval", 另一种转换方式是"i4n1l"和"i4v1l", 然而这个不被允许."intern1l" 和"interv1l"是可以的, 但是并有有效缩短, 所以保持原来字符串.

先为每个字符串找出第一个abbreviation, 如果有冲突, 则继续找. 最后返回.

参考论坛代码

public class Solution {
    public List<String> wordsAbbreviation(List<String> dict) {

        int[] prefix = new int[dict.size()];
        List<String> ans = new ArrayList<String>();
        for(int i=0;i<dict.size();i++){
            prefix[i]=1;
            ans.add(getAbbr(dict.get(i), 1));
        }
        while(true){
            HashSet<Integer> set = new HashSet<Integer>();
            for(int i=0;i<ans.size();i++)
                for(int j=i+1;j<ans.size();j++){
                    if(ans.get(i).equals(ans.get(j))){
                        set.add(i);set.add(j);
                    }
                }
            if(set.isEmpty()) break;
            for(Integer x : set){
                ans.set(x, getAbbr(dict.get(x), ++prefix[x]));
            }
        }
        return ans;
    }

    public String getAbbr(String s, int k){
        if(k>=s.length()-2) return s;
        StringBuilder sb = new StringBuilder();
        sb.append(s.substring(0,k));
        sb.append(s.length()-k-1);
        sb.append(s.charAt(s.length()-1));
        return sb.toString();
    }
}

Student Attendance Record I

匹配连续3个LLL或两个A，学习regex使用，.*匹配0个或任意多个字符

public class Solution {
    public boolean checkRecord(String s) {
        return !s.matches(".*LLL.*|.*A.*A.*");
    }
}