Topics
In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Example 1:
Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Note:
- The input will only have lower-case letters.
- 1 <= dict words number <= 1000
- 1 <= sentence words number <= 1000
- 1 <= root length <= 100
- 1 <= sentence words length <= 1000
题目大意如下：
给定一个字符数组作为字典，字典内的所有字符串称为 root，能够由 root 和其他单词组成的单词称为 successor
比如，root an ，可以和单词 other 组成另一个单词 another。单词 another 就成为 root an 的一个 successor
现在给一个全是有小写字母组成的句子，找到句子中的 successor 并替换成对应的 root ，然后输出替换后的句子， 如果一个单词有多个 root 单词的话，应替换成长度最小的 root
这题的思路大致如下
我可以把句子按空格 " " 分割成一个个单词，然后对每个单词去 dict 数组里找是否有匹配的，若有则替换，否则不替换
因为 dict 的长度范围为 [1, 1000] ，句子单词数范围也为 [1, 1000]，如果用二重循环暴搜的话，可能会超时。
因此我们需要对 dict 做个优化，我们可以以每个单词的首字母为分组，这样在对句子中的单词进行判断时，
只需要根据首字母找到对应的分组，对这个组内的 root 进行查找，这样会更快。此外如果有多个 root 匹配上了的话，就还需从中选出长度最小的 root 进行替换
最后再把字符串数组变成字符串返回即可
kotlin 代码如下
/**
* 124 / 124 test cases passed.
* Status: Accepted
* Runtime: 444 ms
*/
class Solution {
fun replaceWords(dict: List<String>, sentence: String): String {
val store = dict.groupBy { it[0] }
return sentence.split(" ")
.map { word ->
if (store.containsKey(word[0])) {
store[word[0]]!!
.filter { word.startsWith(it) }
.let { if (it.isEmpty()) word else it.minBy { it.length } }
} else word
}.joinToString(" ")
}
}