290. Word Pattern

Easy

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

Example 3:

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

Constraints:

  • 1 <= pattern.length <= 300

  • pattern contains only lower-case English letters.

  • 1 <= s.length <= 3000

  • s contains only lowercase English letters and spaces ' '.

  • s does not contain any leading or trailing spaces.

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

解鑌

ζ™‚ι–“θ€‡ι›œεΊ¦ O(n)

func wordPattern(pattern string, s string) bool {
    words := strings.Fields(s)
    if len(words)!=len(pattern) { return false }
    
    m := make(map[uint8]string)
    m2 := make(map[string]uint8)
    
    for i:=0; i<len(words); i++ {
        if val, ok := m[pattern[i]]; ok {
            if val!=words[i] {
                return false
            }
        } else {
            m[pattern[i]] = words[i]
        }
        
        if val, ok := m2[words[i]]; ok {
            if val != pattern[i] {
                return false
            }
        } else {
            m2[words[i]] = pattern[i]
        }
    }
        

    return true
}

Last updated