All problems

Word Pattern

Easy · hash map

You are given a string pattern made of lowercase letters, and a sentence s made of lowercase words separated by single spaces.

The sentence follows the pattern if you can pair each letter of the pattern with a word so that:

• the letter at position i of the pattern is paired with the word at position i of the sentence,
• a letter is always paired with the same word, and
• two different letters are never paired with the same word.

Return true if the sentence follows the pattern, and false otherwise. If the pattern has a different number of letters than the sentence has words, the answer is false.

Examples

Example 1

Input: pattern = "abba", s = "red blue blue red"

Output: true

Pair a with red and b with blue.

Example 2

Input: pattern = "abba", s = "red blue blue green"

Output: false

The first and last letters are both a, but the first and last words differ.

Example 3

Input: pattern = "abab", s = "go go go go"

Output: false

Letters a and b would both have to be paired with go.

Constraints

• 1 <= len(pattern) <= 2000
• pattern contains only lowercase English letters.
• s contains only lowercase English letters and single spaces, with no space at the start or end.
• Every word in s has between 1 and 10 letters.
• s has between 1 and 2000 words.