290. Word Pattern

Problem

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:

Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Note:

You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Problem Summary

Given a pattern string, determine whether the string and the given pattern string follow the same pattern.

Solution Approach

This problem can be solved with 2 maps. One map records the matching relationship between the pattern and the string, and the other map records the matching relationship between the string and the pattern. Why is it necessary to record the bidirectional relationship? Because in Example 4, a corresponds to dog; at this point, if b also corresponds to dog, it is incorrect, so we need to query from dog whether it has already been matched with some pattern. Therefore, a bidirectional relationship is needed.

Code

package leetcode

import "strings"

func wordPattern(pattern string, str string) bool {
	strList := strings.Split(str, " ")
	patternByte := []byte(pattern)
	if pattern == "" || len(patternByte) != len(strList) {
		return false
	}

	pMap := map[byte]string{}
	sMap := map[string]byte{}
	for index, b := range patternByte {
		if _, ok := pMap[b]; !ok {
			if _, ok = sMap[strList[index]]; !ok {
				pMap[b] = strList[index]
				sMap[strList[index]] = b
			} else {
				if sMap[strList[index]] != b {
					return false
				}
			}
		} else {
			if pMap[b] != strList[index] {
				return false
			}
		}
	}
	return true
}