Problem#
給你一個字串 pattern 和字串 s 問你 pattern 和 s 是不是 full match
1 | "abba" -> "dog cat cat dog" |
1 <= pattern.length <= 3001 <= s.length <= 3000
想法#
維護兩個資料結構紀錄 s 映射到 pattern (A) 以及 pattern 映射到 s (B)。
把輸入用空白切開，掃過一遍，如果 word 沒出現在 A 中且沒出現在 B 中(代表新的word) 則紀錄。如果沒出現在 A 中但有出現在 B 中，則代表這次的word跟之前紀錄的不同，代表不可能符合 pattern 返回 false。如果 word 有出現在 A 中，則判斷 A 存的字元是否等於 pattern[i]
- 時間複雜度: $\mathcal{O}(n\log{n})$
- 空間複雜度: $\mathcal{O}(n)$
AC Code#
心得#
這題測資輸入很鳥= =