Word Pattern Matching

Given a pattern string and a sentence, determine whether the sentence follows the specified pattern. In this problem, each character in the pattern is mapped to a word in the sentence. The mapping must be bijective, meaning that:

• If a character c in the pattern appears multiple times, then the corresponding words in the sentence must be the same.
• If two different characters are mapped, they must correspond to two different words.

This can be formally expressed as: $$\forall i,j,\;\text{if } pattern[i]=pattern[j] \text{ then } words[i]=words[j]$$ and vice versa. For example, pattern "abba" and sentence "dog cat cat dog" is valid, whereas pattern "abba" and sentence "dog cat cat fish" is not.

inputFormat

The input is provided via standard input (stdin) as two separate lines:

1. The first line contains a non-empty string representing the pattern.
2. The second line contains a sentence with words separated by spaces.

outputFormat

Output to standard output (stdout) a single line: true if the sentence follows the given pattern, and false otherwise.

abba
dog cat cat dog

true