LeetCode.290 单词规律

题目描述：

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 的特性。

参考

单词规律 - 单词规律 - 力扣（LeetCode） (leetcode-cn.com)