This is the 18th day of my participation in the August Genwen Challenge.More challenges in August

Title description:

290. Word Rules – LeetCode (leetcode-cn.com)

Given a pattern and a string STR, determine whether STR follows the same pattern.

By following, we mean matching exactly. For example, there is a bidirectional connection between every letter in pattern and every non-empty word in the string STR.

Example 1:

Input: pattern = "abba", STR = "dog cat cat dog" Output: trueCopy the code

Example 2:

Enter :pattern = "abba", STR = "dog cat cat fish" Output: falseCopy the code

Example 3:

Input: pattern = "aAAA ", STR = "dog cat cat dog" Output: falseCopy the code

Example 4:

Enter: pattern = "abba", STR = "dog dog dog dog" Output: falseCopy the code

Note: You can assume that Pattern contains only lowercase letters and that STR contains lowercase letters separated by a single space.

Thought analysis

Hash table

This is a string mapping problem.

When our pattern is split, each word in the STR corresponding to each character is split in pairs.

This is simple: we iterate over characters in pattern to match words in STR. If there is a conflict, the condition is not satisfied.

AC code

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}}Copy the code

Hash table optimization scheme

/**
 * 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?
Copy the code

We see that hash tables have a property that when put returns the previous value, if there is one.

Let’s just look at the code.

AC code

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}}Copy the code

explain

If the key does not exist, null is returned. If the key exists, return the value corresponding to the previous key. For example, if pattern = "abba" and STR = "dog cat cat dog", map.put('a',0) returns null, and map.put("dog",0) returns null. Put ('b',1) returns null, map.put("cat",1) returns null, both equal; Third time: map.put('b',2) returns 1, map.put("cat",2) returns 1, both equal; Fourth time: map.put('a',3) returns 0, map.put("dog",3) returns 0, both equal, and the result is true. For example, if pattern = "abba" and STR = "dog cat cat fish", map.put('a',0) returns null, and map.put("dog",0) returns null. Put ('b',1) returns null, map.put("cat",1) returns null, both equal; Third time: map.put('b',2) returns 1, map.put("cat",2) returns 1, both equal; Fourth time: map.put('a',3) returns 0, map.put("fish",3) returns null, the two are not equal, false.Copy the code

conclusion

The idea is simple. The second solution needs to use the features of HashMap.

reference

Word Rules – Word Rules – LeetCode (leetcode-cn.com)