290.Word_Pattern(Easy).md

290. Word Pattern (Easy)

Date and Time: Nov 15, 2024, 14:10 (EST)

Link: https://leetcode.com/problems/word-pattern/

Question:

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. Specifically:

• Each letter in pattern maps to exactly one unique word in s.

• Each unique word in s maps to exactly one letter in pattern.

• No two letters map to the same word, and no two words map to the same letter.

Example 1:

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

Output: true

Explanation:
The bijection can be established as:

• 'a' maps to "dog".
• 'b' maps to "cat".

Example 2:

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

Output: false

Example 3:

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

Output: false

Edge Case 1:

Input: pattern = "abb", s = "dog cat cat fish"

Output: false

Explanation: the length of pattern does not equal to the length of s

Edge Case 2:

Input: pattern = "abba", s = "dog dog dog dog"

Output: false

Explanation: Each letter in pattern maps to exactly one unique word in s.

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.

Walk-through:

We can build a hashmap to create mapping of each letter in pattern with word in s. If a letter exists in hashmap{}, we check if the previous mapping matches the current word we are checking.

Notice there are some special cases we need to consider: 1. when the length of pattern does not match the length of s, we won't be able to match each of them, we should return False. 2. The question asks "there is a bijection between a letter in pattern and a non-empty word in s", so we can use set() to detect if we have duplicate word by comparing the length equals or not after we set() pattern and s.

Python Solution:

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        # Map each char in pattern with a word in s
        # If a char from pattern in the hashmap, check the mapping hashmap[char] == s[i] or not

        # TC: O(n), n = len(pattern), SC: O(n)
        hashmap = {}
        s = list(s.split())
        # When length of pattern is not equal to len(s)
        if len(pattern) != len(s):
            return False
        # Make sure each letter in pattern maps to exactly one unique word in s
        if len(set(pattern)) != len(set(s)):
            return False
        for i in range(len(pattern)):
            char = pattern[i]
            # If char in hashmap, we check the mapping
            if char in hashmap and hashmap[char] != s[i]:
                return False
            # If char not in hashmap, we add the mapping
            else:
                hashmap[char] = s[i]
        return True

Time Complexity: $O(n)$, n is len(s).
Space Complexity: $O(n)$