205. 同构字符串

290. 单词规律

示例 1:
输入：s = "egg",t = "add"
输出：true

复杂度分析

  • 时间复杂度：O(n)，其中 nn 为字符串的长度。我们只需同时遍历一遍字符串 ss 和 tt 即可。

  • 空间复杂度：O(∣Σ∣)，其中Σ 是字符串的字符集。哈希表存储字符的空间取决于字符串的字符集大小，最坏情况下每个字符均不相同，需要 O(∣Σ∣) 的空间。

    1. //双哈希表 + 建立互相映射
    2. func isIsomorphic(s string, t string) bool {
    3.   s2t := map[byte]byte{}
    4.   t2s := map[byte]byte{}
    6.   for i := range s {
    7.       x, y := s[i], t[i]
    8.       if s2t[x] > 0 && s2t[x] != y || t2s[y] > 0 && t2s[y] != x {
    9.           return false
    10.       }
    12.       s2t[x] = y
    13.       t2s[y] = x
    14.   }
    15.   return true
    16. }

示例1:
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
复杂度分析

  • 时间复杂度：O(n + m)，其中 n 为 pattern 的长度，m 为str 的长度。插入和查询哈希表的均摊时间复杂度均为 O(n + m)。每一个字符至多只被遍历一次。

  • 空间复杂度：O(n+m)，其中 n 为pattern 的长度，m 为str 的长度。最坏情况下，我们需要存储 pattern 中的每一个字符和 str 中的每一个字符串。

    时空O（m+n）
func wordPattern(pattern string, s string) bool {
  word2ch := map[string]byte{}
  ch2word := map[byte]string{}
  words := strings.Split(s, " ")

  if len(pattern) != len(words) {
      return false
  }

  for i, word := range words {
      ch := pattern[i]
      if word2ch[word] > 0 && word2ch[word] != ch || ch2word[ch] != "" && ch2word[ch] != word {
          return false
      }

      word2ch[word] = ch
      ch2word[ch] = word
  }
  return true
}