Why this matters
Two common checks ask whether two sequences have the same shape. Do egg and add have the same shape? Does the sentence dog cat cat dog follow the pattern abba? In both checks each symbol must always pair with the same partner, and two different symbols may not share one partner. Interview questions use these two checks often, because a correct answer needs two maps in one loop.
The sliding window lesson before this one counts letters in a range. This lesson uses letters and words as map keys, and it checks a pairing rather than a count.
The idea: a one-to-one pairing
Two strings are isomorphic when they have the same length and you can replace every letter of the first string with a letter of the second so that two rules hold.
- Each letter in the first string always becomes the same letter in the second string.
- Two different letters in the first string never become the same letter in the second string.
Rule 1 is the forward check. Rule 2 is the backward check. Take egg and add. The e becomes a, the first g becomes d, and the second g becomes d again. The forward check passes, because each letter has one partner. The backward check passes too, because a came only from e, and d came only from g. The answer is true.
Now take foo and bar. The f becomes b, and the o becomes a. The next o must become r, but it already became a. The forward check fails, so the answer is false.
Take ab and aa. The a becomes a, and the b becomes a. The forward check passes, since each letter of the first string has one partner. The backward check fails, because the letter a in the second string came from both a and b. The answer is false.
A single map from the first string to the second catches the foo case but not the ab case. That is why the solution uses two maps. One map records what each letter of the first string became. The other records which letter of the first string each letter of the second string came from.
Word patterns use the same two maps
A word pattern is a string of letters such as abba, and a sentence of words. Each letter in the pattern must always stand for the same word, and each word must come from only one letter. The sentence dog cat cat dog fits abba. The a stands for dog, the b stands for cat, and both repeat correctly. The sentence dog dog dog dog does not fit, because both a and b would have to stand for dog.
A pattern can match only when it has exactly as many letters as the sentence has words. Check that first.
Two maps, and why find is used
The code below uses two maps. The names sToT and tToS mean "first string to second string" and "second string to first string". Each map is looked up with find, not with map[key]. The reason is that map[key] creates an entry when the key is missing, with a default value. Creating an entry during a check is a silent change to the map. find returns a position called end() when the key is missing, and it changes nothing.
Example one: isomorphic strings
The program checks six pairs and prints a result for each. The line cout << boolalpha; makes the program print true and false rather than 1 and 0.
The output is:
egg/add: true
foo/bar: false
paper/title: true
badc/baba: false
ab/aa: false
empty: trueThe loop goes through the two strings one position at a time. At each position it has one letter a from the first string and one letter b from the second.
The first if is the forward check. If the first string's letter a already has a partner in sToT, and that partner is not b, the answer is false.
The second if is the backward check. If the second string's letter b already has a partner in tToS, and that partner is not a, the answer is false.
After both checks pass, the program records the pair in both maps. A letter that appears again later will then be checked against the recorded partner.
The empty pair is true. Two empty strings have no letters that could conflict, so the loop never runs.
For badc and baba, the first two pairs are fine: b with b, and a with a. The third pair, d with b, breaks the backward rule, because b in the second string already came from b in the first string. The d cannot also map to b.
Example two: word patterns
The second program takes a pattern and a sentence. It splits the sentence into words, then applies the same two checks, with the letters of the pattern and the words of the sentence as the two sides.
Splitting the sentence uses istringstream. This is a stream object that reads from a string the same way cin reads from the keyboard. The expression in >> word reads one word, skipping any spaces before it. Words are separated by one or more spaces, so the line while (in >> word) gives the same words for dog cat and dog cat.
The output is:
abba dog cat cat dog: true
abba dog cat cat fish: false
aaaa dog cat cat dog: false
abba dog dog dog dog: false
abc b c a (extra spaces): true
ab dog dog: falseThe first line is the egg style example from the start of this lesson, with words in place of letters. In the second line, the fourth word fish breaks the rule that a stands for dog. The third line fails because aaaa says all four words must be the same, but dog and cat differ. The fourth line fails the backward rule, since dog would stand for both a and b.
The fifth line shows that extra spaces do not change the words. The pattern abc matches b c a, because the three words are different.
The last line has two letters and two words, and both words are dog. The forward check passes, since a and b each have one word. The backward check fails, because dog would stand for both a and b.
Notice the variable word in the loop is declared as const string&. That means it refers to the word stored in words without copying it. The check does not change the word, so const is correct.
Example three: finding where the rule breaks
A yes or no answer is often not enough. When a check fails, a program may need to know which position broke the rule. The next program returns the position of the first conflict. It returns an optional<size_t>. An optional either holds a position or holds nothing. A position means "the rule breaks here". Nothing means "no conflict was found".
The inputs must have the same length. The function does not check that, so the caller must check it first.
The output is:
foo/bar: 2
ab/aa: 1
abca/zbxz: 99
abab/cdcd: 99
ab/cc: 1
egg/add: 99Positions start at 0, so the first letter is at position 0. In foo and bar, the conflict is at position 2, which is the second o. In ab and aa, the conflict is at position 1, which is the b.
The value 99 is used only in main to print something when there is no conflict. The number 99 is not a position in these strings. The check value_or(99) returns the stored position, or 99 when the optional is empty.
The pairs abca and zbxz have no conflict. The a becomes z at both places where it appears, and z came only from a. The b maps to b, and the c maps to x.
Common mistakes
Mistake one: using only one map
A single map from the first string to the second catches a letter that changes its partner. It does not catch two letters that share one partner. The program below uses one map and checks ab and aa.
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
bool oneMapOnly(const string& s, const string& t) {
if (s.size() != t.size()) return false;
unordered_map<char, char> sToT;
for (size_t i = 0; i < s.size(); ++i) {
char a = s[i];
char b = t[i];
auto found = sToT.find(a);
if (found != sToT.end() && found->second != b) return false;
sToT[a] = b;
}
return true;
}
int main() {
cout << boolalpha;
cout << "ab/aa: " << oneMapOnly("ab", "aa") << "\n";
}The output is:
ab/aa: trueThe correct answer is false. The program says true because it never checks whether a in the second string already came from some other letter. Adding the second map, and its check, fixes the problem.
Mistake two: skipping the length check for word patterns
The number of letters in the pattern and the number of words must match. Without this check, the loop reads past the end of the list of words. The program below leaves out the check and runs the pattern abc against two words.
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
bool wordPatternNoLengthCheck(const string& pattern, const string& text) {
vector<string> words;
istringstream in(text);
string word;
while (in >> word) words.push_back(word);
unordered_map<char, string> letterToWord;
unordered_map<string, char> wordToLetter;
for (size_t i = 0; i < pattern.size(); ++i) {
char letter = pattern[i];
const string& w = words[i];
auto a = letterToWord.find(letter);
if (a != letterToWord.end() && a->second != w) return false;
auto b = wordToLetter.find(w);
if (b != wordToLetter.end() && b->second != letter) return false;
letterToWord[letter] = w;
wordToLetter[w] = letter;
}
return true;
}
int main() {
cout << boolalpha << wordPatternNoLengthCheck("abc", "dog cat") << "\n";
}On the Ubuntu g++ 15 build used for this lesson, the program stops with this message. The middle of the line is cut here, and it repeats the function signature.
/usr/include/c++/15/bits/stl_vector.h:1263: ... operator[](size_type) [...]: Assertion '__n < this->size()' failed.The process ends with exit code 134, which means it was stopped by an abort signal. Other builds may not check the index at all. In that case the program reads memory that does not belong to the list, and the result is unpredictable. The fix is the first check in wordPattern in example two.
Mistake three: calling a split method that does not exist
C++ strings have no split method. A program that calls one does not compile, and the compiler says so. The file below tries to split a sentence the way some other languages allow.
#include <string>
#include <vector>
using namespace std;
int main() {
string text = "dog cat cat dog";
vector<string> words = text.split(' ');
return static_cast<int>(words.size());
}Compiled with g++ -std=c++20 -Wall, the compiler prints this error:
split_words.cpp: In function ‘int main()’:
split_words.cpp:7:33: error: ‘std::string’ {aka ‘class std::__cxx11::basic_string<char>’} has no member named ‘split’
7 | vector<string> words = text.split(' ');
| ^~~~~The fix is to read the words with istringstream, as in example two.
Practice
Exercise 1. Are abca and zbxz isomorphic?
Show the answer
Yes. The program in example three prints 99 for this pair, which means it found no conflict. The a becomes z at both places, and no two letters of the first string share a partner.
Exercise 2. For ab and cc, at which position does the first conflict happen? Positions start at 0.
Show the answer
Position 1. The a becomes c at position 0. At position 1, the b would also become c. The backward check fails, because the letter c already came from a. The program in example three prints 1 for this pair.
Exercise 3. Does the pattern xyx match the sentence cat dog cat?
Show the answer
Yes. The x stands for cat at both places where it appears, and the y stands for dog. The program in example two gives true for the same input.
Exercise 4. Does the pattern xyx match the sentence cat dog bird?
Show the answer
No. The first x stands for cat, but the last x stands for bird. The forward check fails at the third word. The program gives false for this input.
Exercise 5. Does the pattern abab match the sentence cat dog dog cat?
Show the answer
No. The a stands for cat at position 0. At position 2 the a would have to stand for dog, which breaks the rule. The check fails at the third word, so the answer is false.
Summary
- Two maps, one for each direction, check a one-to-one pairing. One map alone misses two letters that share a partner.
- Look up keys with
find, so a check does not create new entries in the maps. - A word pattern needs the same number of letters and words, and it follows the same two checks.
istringstreamsplits a sentence into words, because C++ strings have nosplitmethod.