单词缩写集 · word abbreviation set

［抄题］：

一个单词的缩写根据以下的形式。下面是一些缩写的例子

a) it                      --> it    (没有缩写)

     1

b) d|o|g                   --> d1g

              1    1  1

     1---5----0----5--8

c) i|nternationalizatio|n  --> i18n

              1

     1---5----0

d) l|ocalizatio|n          --> l10n

假设你有一个字典和给你一个单词，判断这个单词的缩写在字典中是否是唯一的。当字典中的其他单词的缩写均与它不同的时候，这个单词的缩写是唯一的.

[暴力解法]：

1把缩写全部存一遍，再一个个搜索是否为重复，不重复unique

时间分析：

空间分析：

［思维问题］：

2有单词重复但是缩写相同的情况，此时仍为unique。

但是分类讨论也不好，把两种unique合并：单词出现次数和缩写出现次数相同

［一句话思路］：

把原单词和缩写分别放在两张哈希表来查，不要一起查。

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

要把字符串拼起来时，直接用+即可。取出字母用的是charAt(i)的方法
hash用getOrDefault(d, 0)+1来存数，记得加括号写0

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

返回单词可以用"" +的形式来直接拼接

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

hashmap：单词+出现次数，重要的是单词。用两个来比较出现的次数是否相同。

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

很多abbreviation的题。应该都是单独分离一个abbr函数，再用“”空格来拼接

[代码风格] ：

整体的结构是类中包括成员变量+多个方法，不要把成员变量写在某一个方法里

public class ValidWordAbbr {

    /*

    * @param dictionary: a list of words

    */

    HashMap<String, Integer> dict = new HashMap<>();

    HashMap<String, Integer> abbr = new HashMap<>();

     public ValidWordAbbr(String[] dictionary) {

        for (String d : dictionary) {

            dict.put(d, dict.getOrDefault(d, 0) + 1);//

        }

        for (String d : dictionary) {

            abbr.put(getAbbr(d), abbr.getOrDefault(getAbbr(d), 0) + 1);

        }

    }

    /*

     * @param word: a string

     * @return: true if its abbreviation is unique or false

     */

    public boolean isUnique(String word) {

        return (dict.get(word) == abbr.get(getAbbr(word)));

    }

    //getAbbr

    private String getAbbr(String word) {

        if (word.length() <= 2) {//<=

            return word;//

        }

        return "" + word.charAt(0) + (word.length() - 2) + word.charAt(word.length() - 1);

    }

}

/**

 * Your ValidWordAbbr object will be instantiated and called as such:

 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);

 * boolean param = obj.isUnique(word);

 */

巴特西

单词缩写集 · word abbreviation set

最新文章

热门文章