10k

288. Unique Word Abbreviation

Published on

Question

The problem is that given an array of characters, the title says to construct a dictionary of them, and the construction rule is "abbreviation". An abbreviation is the length of the middle of the first and last letter plus its middle string (excluding the first and last letter), for example international is abbreviated to i18n. The abbreviation of a string of length 2 is itself.

There are quite a few pitfalls in this topic. For example, the string of length 1 is not mentioned, here you can check with the questioner, I was practicing on my own, so I assumed that he is also itself (and the final result is true).

The other is to implement his isUnique method. The rule is two, one of which is satisfied, either he is not in the key of this dictionary (i.e. new field) or it is a field that already appears and both key and value already exist in the dictionary.

Algorithm

The topic has been given to let use a dictionary, in Java you can initially try to use a hashmap.

I started with the idea of Map<String, List<String>> map;, list all the words that match his key abbreviation.

If purely to do the problem, you can write code 2, space and time are prompted, because his processing is to meet the duplicate key directly to the abbreviation of the key set to unavailable (value is empty), so that the subsequent in the judgment of the time can also be relatively simple to use.

I think in the actual application, including the meaning of the question, a dictionary is required to save the key value information, but isUnique function in order to calculate the convenience of the data will already exist directly to the empty string, I think it is a bit strange, I think this topic is also a reason for the low score.

However, in my own code 1, I fell into a misunderstanding for a while, and did not use the charAt method but used substring when taking the characters, and needed to think about the startIndex and endIndex, while charAt is simpler, and the time complexity of charAt is O(1) compared to the other one is O(n).

Code 1

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

    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String word : dictionary) {
            String abbr = getAbbr(word);
            if (!map.containsKey(abbr)) {
                map.put(abbr, new ArrayList<>());
            }
            if (!map.get(abbr).contains(word)) {
                map.get(abbr).add(word);
            }
            
        }
    }
    
    private String getAbbr(String word) {
        if (word == null || word.length() == 0) return "";
        if (word.length() <= 2) return word;
        return word.substring(0, 1) + String.valueOf(word.length() - 2) + word.substring(word.length() - 1, word.length());
    }
    
    public boolean isUnique(String word) {
        String abbr = getAbbr(word);
        for (List<String> words : map.values()) {
            if (words.contains(word) && words.size() == 1) {
                return true;
            }
        }
        return !map.containsKey(abbr);
    }
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
 * boolean param_1 = obj.isUnique(word);
 */

Code 2

class ValidWordAbbr {
    HashMap<String, String> map;

    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String s : dictionary) {
            if (!map.containsKey(getKey(s))) {
                map.put(getKey(s), s);
            } else {
                if (!map.get(getKey(s)).equals(s)) {
                    map.put(getKey(s), "");
                }
            }
        }
    }
    
    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;
        String length = s.length() - 2 + "";
        return s.charAt(0) + length + s.charAt(s.length() - 1);
    }
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
 * boolean param_1 = obj.isUnique(word);
 */

问题

这个问题是题目说给定一个字符数组，将他们构造一个字典，构造规则是“缩写”。缩写就是取首尾字母中间加他的中间字符串（除去首尾字母）的长度，例如international被缩写为i18n。长度为2的字符串缩写就是他本身。

这个题目有挺多的陷阱。比如长度为1的字符串没提，这里可以和出题人确认，我是自己练习，所以假定了他也是它本身（最后结果也确实如此）。

另外就是实现他的isUnique方法。这个规则是两个，满足一个就可以，要么是他不在这个字典的key中（即新字段）；要么是已经出现过的字段并且key 和value都已经存在于字典。

算法

这个题目已经给了让用dictionary，在Java中可以初步尝试使用hashmap。

我一开始想的是Map<String, List<String>> map;，list存所有符合他的key这个缩写的word。最后也实现了，但是挺慢的。

如果纯为了做题，就可以写出代码2，空间和时间上都有所提示，因为他的处理是遇到重复的key直接就将这个缩写的key置为了不可用（value为空），这样后续在判断的时候也可以比较简单的利用。

这个题还是要看出题人的意图，我觉得在实际的应用中，包括题意，一个字典是需要保存key value信息的，但是isUnique函数为了计算方便直接将已经存在得数据置为空字符串，个人觉得有点奇怪，估计也是这个题目被打低分的一个原因。

不过在我自己的代码1中，一时竟然陷入了一个误区，在取字符的时候没有用charAt方法而是用了substring，还需要额外想一下startIndex 和endIndex,而charAt就简单一些，而且charAt的时间复杂度是O(1)对比另外一个是O(n)。

代码1

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

    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String word : dictionary) {
            String abbr = getAbbr(word);
            if (!map.containsKey(abbr)) {
                map.put(abbr, new ArrayList<>());
            }
            if (!map.get(abbr).contains(word)) {
                map.get(abbr).add(word);
            }
            
        }
    }
    
    private String getAbbr(String word) {
        if (word == null || word.length() == 0) return "";
        if (word.length() <= 2) return word;
        return word.substring(0, 1) + String.valueOf(word.length() - 2) + word.substring(word.length() - 1, word.length());
    }
    
    public boolean isUnique(String word) {
        String abbr = getAbbr(word);
        for (List<String> words : map.values()) {
            if (words.contains(word) && words.size() == 1) {
                return true;
            }
        }
        return !map.containsKey(abbr);
    }
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
 * boolean param_1 = obj.isUnique(word);
 */

代码2

class ValidWordAbbr {
    HashMap<String, String> map;

    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String s : dictionary) {
            if (!map.containsKey(getKey(s))) {
                map.put(getKey(s), s);
            } else {
                if (!map.get(getKey(s)).equals(s)) {
                    map.put(getKey(s), "");
                }
            }
        }
    }
    
    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;
        String length = s.length() - 2 + "";
        return s.charAt(0) + length + s.charAt(s.length() - 1);
    }
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
 * boolean param_1 = obj.isUnique(word);
 */
Thoughts? Leave a comment