leecode290单词规律

leecode

题目描述

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/word-pattern 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

哈希法 理解题目:需要单词完全一样才是一个字母,我开始以为是首字母一样就算,结果一直通不过. 我们采用哈希表双向映射 的方法来解决

1. 将s剪切成单个单词,用go的内置函数/并且长度必须相同

// 剪切每一个单词
 str := strings.Split(s, " ")
 // 如果长度不相同返回false
 if len(str) != len(pattern) {
  return false
 }

2. 建立双向映射的哈希表

//第一个储存pattern中的字符;第二个储存s中单个单词
 m1 := make(map[byte]string)
 // 双向映射
 m2 := make(map[string]byte)

3. 循环遍历str与pattern,并填充查找映射,并且当映射不对时返回false(核心)

for i := 0; i < len(pattern); i++ {
  // 为空时建立双向匹配
  if m1[pattern[i]] == "" && m2[str[i]] == 0 {
   m1[pattern[i]] = str[i]
   m2[str[i]] = pattern[i]
   // 双向匹配成功继续
  } else if m1[pattern[i]] == str[i] && m2[str[i]] == pattern[i] {
   continue
   // 不成功返回false
  } else {
   return false
  }
 }

执行结果

法1

func wordPattern(pattern string, s string) bool {
 //hash法
 // 剪切每一个单词
 str := strings.Split(s, " ")
 // 如果长度不相同返回false
 if len(str) != len(pattern) {
  return false
 }
 //第一个储存pattern中的字符;第二个储存s中单个单词
 m1 := make(map[byte]string)
 // 双向映射
 m2 := make(map[string]byte)

 for i := 0; i < len(pattern); i++ {
  // 为空时建立双向匹配
  if m1[pattern[i]] == "" && m2[str[i]] == 0 {
   m1[pattern[i]] = str[i]
   m2[str[i]] = pattern[i]
   // 双向匹配成功继续
  } else if m1[pattern[i]] == str[i] && m2[str[i]] == pattern[i] {
   continue
   // 不成功返回false
  } else {
   return false
  }
 }
 return true
}

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.8 MB , 在所有 Go 提交中击败了 96.65% 的用户 通过测试用例： 41 / 41 炫耀一下: