# String Matching With Transliteration
# You may or may not know that Google Docs has a feature to find and replace even for characters
# not in the standard English alphabet ([A-Z]). To do this, we first need a transliteration map, e.g.
# Keys are single non-standard-English characters, values are
# strings consisting of standard English characters.
tl_map = {
"ë": "e",
"é": "e",
"û": "u",
"æ": "ae",
"ž": "zed", # Made up, meant as a harder case for testing.
...
}
1. Given a haystack string and a needle string and the transliteration mapping,
return whether the needle is matched within the haystack.
Example 1:
haystack: "I love crème brûlée"
needle: "eme"
return: True
Example 2:
haystack: "I love crème brûlée"
needle: "ême"
return: True
Example 3:
haystack: "Ole Gunnar Solskjær is amazing"
needle: "Solskja"
return: True
Example 4:
haystack: "Ole Gunnar Solskjær is amazing"
needle: "Solskjear"
return: False
This Google problem asks you to determine whether a“needle”appears in a“haystack,”but with a twist: non-standard characters such as é, ë, æ, or å must be converted according to a given transliteration map before matching. The map can map one character to multiple English characters (e.g., “æ” → “ae”), so matching is not just one-to-one replacement but requires expanding characters properly before comparing segments. The challenge lies in performing transliteration consistently for both haystack and needle—while keeping the algorithm efficient enough for large strings.
END
