LeetCode.290 单词规律
站长
· 阅读数 8
题目描述：
290. 单词规律 - 力扣（LeetCode） (leetcode-cn.com)
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
示例 2:
输入:pattern = "abba", str = "dog cat cat fish"
输出: false
示例 3:
输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false
示例 4:
输入: pattern = "abba", str = "dog dog dog dog"
输出: false
说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
思路分析
哈希表
根据题意和示例我们不难发现，这就是一个字符串映射的问题。
我们的 pattern 拆分后，每个字符对应的 str 中的拆分的每个单词都是成对的。
这样就很简单了，我们遍历 pattern 中的字符，去匹配 str 中的单词，如果发生冲突，就条件不满足。
AC代码
class Solution {
fun wordPattern(pattern: String, s: String): Boolean {
if (pattern.isEmpty() || s.isEmpty()) return false
val list = s.split(" ")
if (pattern.length != list.size) return false
val mapChar = mutableMapOf<Char, String>()
val mapStr = mutableMapOf<String, Char>()
for (i in list.indices) {
val char = pattern[i]
val str = list[i]
if (mapChar[char] == null && mapStr[str] == null) {
mapChar[char] = str
mapStr[str] = char
} else if (mapChar[char] != null
&& mapStr[str] != null
&& mapChar[char] == str
&& mapStr[str] == char) {
continue
} else {
return false
}
}
return true
}
}
哈希表优化方案
/**
* Associates the specified [value] with the specified [key] in the map.
*
* @return the previous value associated with the key, or `null` if the key was not present in the map.
*/
public fun put(key: K, value: V): V?
我们看到哈希表有个特性，put 的时候会返回前一个 value，假如有的话。
直接看代码吧。
AC代码
class Solution {
fun wordPattern(pattern: String, s: String): Boolean {
val array = s.split(" ")
if (pattern.length != array.size) {
return false
}
val map = mutableMapOf<Any, Int>()
for (i in 0 until pattern.length) {
if (map.put(pattern[i], i) != map.put(array[i], i)) {
return false
}
}
return true
}
}
解释
如果key不存在，插入成功，返回null；如果key存在，返回之前此key对应的value。
以pattern = "abba", str = "dog cat cat dog"为例，
第1次：map.put('a',0)返回null，map.put("dog",0)返回null，两者相等；
第2次：map.put('b',1)返回null，map.put("cat",1)返回null，两者相等；
第3次：map.put('b',2)返回1，map.put("cat",2)返回1，两者相等；
第4次：map.put('a',3)返回0，map.put("dog",3)返回0，两者相等，
结果为 true。
以pattern = "abba", str = "dog cat cat fish"为例，
第1次：map.put('a',0)返回null，map.put("dog",0)返回null，两者相等；
第2次：map.put('b',1)返回null，map.put("cat",1)返回null，两者相等；
第3次：map.put('b',2)返回1，map.put("cat",2)返回1，两者相等；
第4次：map.put('a',3)返回0，map.put("fish",3)返回null，两者不相等，
结果为 false。
总结
思路简单，解法二需要用到 HashMap 的特性。