290. Word Pattern

LeetCode 290. Word Pattern

Description

Given a pattern and a string s, find if s 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 s.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= pattern.length <= 300

• pattern contains only lower-case English letters.

• 1 <= s.length <= 3000

• s contains only lower-case English letters and spaces ' '.

• s does not contain any leading or trailing spaces.

• All the words in s are separated by a single space.

Tags

Hash Table

Solution

See Reference 1.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

func wordPattern(pattern string, s string) bool {
	p2s, s2p, ss := map[byte]string{}, map[string]byte{}, strings.Split(s, " ")
	if len(pattern) != len(ss) {
		return false
	}
	for i := range pattern {
		if len(p2s[pattern[i]]) > 0 && p2s[pattern[i]] != ss[i] || s2p[ss[i]] > 0 && s2p[ss[i]] != pattern[i] {
			return false
		}
		p2s[pattern[i]], s2p[ss[i]] = ss[i], pattern[i]
	}
	return true
}

Reference

1. 205. Isomorphic Strings