Statement▼
You are given a pattern and a string, s. You need to determine whether the string s follows the same pattern.
A string s is said to follow a pattern if a bijection exists between a character in the pattern and a non-empty word in s.
Each character in the
patternmust map to exactly one unique word ins.Each word in
smust map to exactly one unique character inpattern.No two characters map to the same word, and no two words map to the same character.
Constraints:
1≤ pattern.length≤100 The
patterncontains only lowercase English letters.1≤ s.length≤1000 scontains only lowercase English letters and spaces' '.sdoes not contain any leading or trailing spaces.A single space separates all the words in
s.
Solution
The algorithm checks whether a given string of words follows the same pattern as a sequence of characters, ensuring a one-to-one correspondence (bijection) between pattern characters and words. It begins by splitting the string s into individual words and verifying that the number of characters in the pattern matches the number of words; if not, it immediately returns False. Using a hash map, the algorithm records the first index at which each pattern character and word appear by creating unique keys. As it iterates through the words, it checks that the indices associated with a character and its corresponding word remain consistent, ensuring that each character maps to exactly one word and each word maps to exactly one character. If any mismatch occurs in this mapping, return False; otherwise, return True, confirming that the string follows the specified pattern.
The steps of the algorithm are as follows:
Create an empty dictionary
map_indexto store the mapping indices for pattern characters and words.Use
s.split()to divide the string into a list ofwords.If the number of characters in the
patterndoes not equal the number of words, returnFalseimmediately.Iterate through each character–word pair simultaneously using their indices.
For each character
cand wordw, form two distinct keys:char_key = 'char_{}'.format(c)char_word = 'word_{}'.format(w)Assign or compare mapping indices:
If a key does not exist in
map_index, assign its value as the current indexi.After the assignment, compare the stored indices for both keys.
If the indices do not match, return
False(indicating inconsistent mapping).
After processing all pairs without inconsistencies, return
True, confirming that the pattern matches the word sequence correctly.
Let’s look at the following illustration to get a better understanding of the solution: