LC: 291. Word Pattern II
https://leetcode.com/problems/word-pattern-ii/
291. Word Pattern II
Given a pattern and a string s, return true if s matches the pattern.
A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.
Example 1:
Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"Example 2:
Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"Example 3:
Input: pattern = "abab", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "a"
'b' -> "sdasd"
Note that 'a' and 'b' cannot both map to "asd" since the mapping is a bijection.Example 4:
Constraints:
1 <= pattern.length, s.length <= 20patternandsconsist of only lower-case English letters.
The Essence:
Wenn das Präfix eines String zu dem ersten Zeichen des Patterns zugeordnet ist, dann ist das Suffix zu den übrigen Zeichen des Patterns zugeordnet. Man kann also speichern, welcher Teilzeichenfolge das erste Zeichen entspricht, und darüber hinaus überprüfen, ob unter dieser Bedingung das Suffix des String das Pattern noch übereinstimmen kann.
Details:
Da viele Präfixe des Strings für ein Zeichen getestet werden, dann soll eine solche Versuchstruktur an die Backtracking-Technik erinnern. Durch Versuch und Irrtum testet man alle sinnvollen Möglichkeiten, bei welchen die Strings zueinander entsprechen könnten.
Solution(s) and Further Explanation: Default Code:
Last updated