288. 单词的唯一缩写

Posted on | In
Words count in article: 339 | Reading time ≈ 1

题目

一个单词的缩写需要遵循 <起始字母><中间字母数><结尾字母> 这样的格式。

以下是一些单词缩写的范例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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：

1
2
3
4
5
6
给定 dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

解法

解法一：

借助HaspMap，这里需要注意相同的字符串是算作唯一的。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class ValidWordAbbr {
	private Map<String, Set<String>> abbrDict = new HashMap<>();

	public ValidWordAbbr(String[] dictionary) {
		for (String s : dictionary) {
			String abbr = toAbbr(s);
			Set<String> words = abbrDict.containsKey(abbr) ? abbrDict.get(abbr) : new HashSet<>();
			words.add(s);
			abbrDict.put(abbr, words);
		}
	}

	public boolean isUnique(String word) {
		String abbr = toAbbr(word);
		Set<String> words = abbrDict.get(abbr);
		return words == null || (words.size() == 1 && words.contains(word));
	}

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