Consistent Renaming Check
Problem
Two pieces of text have the same shape if one can be turned into the other by renaming characters. A renaming must be consistent in both directions: every occurrence of a character maps to the same replacement, and no two different characters may share a replacement. Decide whether such a renaming exists.
Examples
Input: a = "egg", b = "add"
Output: True
Why: e becomes a and g becomes d, consistentlyInput: a = "foo", b = "bar"
Output: False
Why: o would have to become both a and rInput: a = "ab", b = "aa"
Output: False
Why: edge case, two characters may not collapse onto the same replacementHints
0 / 3
The characters at the same position in the two texts are always paired together, so the whole question is whether those pairings ever contradict each other.
Recording the pairings as you go turns the check into a lookup. One map alone is not enough, because it only catches contradictions in one direction.
Keep two maps, one from each side to the other. At every position, if either map already holds an entry for its character, it must agree with the current partner; otherwise record the new entry. A disagreement in either direction ends the check immediately.
Solution
Walking both texts together pairs up the characters position by position, and a valid renaming means no pair ever contradicts an earlier one. Two maps are needed rather than one: the forward map catches a character being renamed two different ways, and the backward map catches two characters collapsing onto the same replacement. Recording on first sight and comparing thereafter does both checks in one pass. Time is O(n) on average, and space is O(k) for the distinct characters.
def has_consistent_renaming(a, b):
if len(a) != len(b):
return False
forward, backward = {}, {} # a -> b and b -> a pairings seen so far
for x, y in zip(a, b):
# setdefault records a new pairing and returns the one already stored
if forward.setdefault(x, y) != y or backward.setdefault(y, x) != x:
return False
return True
print(has_consistent_renaming("egg", "add")) # -> True
print(has_consistent_renaming("foo", "bar")) # -> False
print(has_consistent_renaming("ab", "aa")) # -> FalseStuck on the idea rather than the code? Hash Table Basics covers it.