您的位置:首页 > 文旅 > 旅游 > 桂林漓江简介_软件测试培训机构学费_seo推广专员工作好做吗_石家庄百度快速排名优化

桂林漓江简介_软件测试培训机构学费_seo推广专员工作好做吗_石家庄百度快速排名优化

2024/12/23 2:45:50 来源:https://blog.csdn.net/coldasice342/article/details/143027407  浏览:    关键词:桂林漓江简介_软件测试培训机构学费_seo推广专员工作好做吗_石家庄百度快速排名优化
桂林漓江简介_软件测试培训机构学费_seo推广专员工作好做吗_石家庄百度快速排名优化

在这里插入图片描述

即判断给定的模式字符串(pattern)和单词字符串(s)是否遵循相同的对应规则。具体来说,就是要判断 pattern 中的字符与 s 中的单词是否存在一一对应的关系,即双射(bijection)。

算法思想:

  1. 输入解析

    • 将字符串 s 按照空格分割成一个单词数组(words),因为 s 是由空格分隔的单词组成。
    • 如果 pattern 的长度和单词数组的长度不相等,直接返回 false。因为字符和单词的数量必须一致,否则无法形成一一对应的关系。
  2. 使用两个哈希表

    • 使用两个哈希表(HashMap)来分别记录字符到单词的映射和单词到字符的映射。
      • charToWord 用于存储模式字符串中的字符与单词的对应关系。
      • wordToChar 用于存储单词与模式字符的对应关系。
  3. 遍历模式字符串和单词数组

    • 对模式字符串的每个字符和对应的单词进行遍历。
    • 如果字符 c 已经在 charToWord 中有映射关系:
      • 检查其映射的单词是否与当前单词一致。如果不一致,返回 false
    • 如果字符 c 没有映射关系:
      • 检查当前单词是否已经被映射到某个字符。如果已经被映射,返回 false
      • 如果没有被映射,则建立字符与单词的双向映射关系,将字符和单词互相映射。
  4. 一致性检查

    • 遍历完所有字符和单词后,如果所有映射关系都满足规则,则返回 true,否则返回 false

具体步骤的中文解释:

  1. 首先将字符串 s 分割成单词数组 words,并检查 patternwords 的长度是否相等。如果长度不相等,则无法匹配,直接返回 false
  2. 使用两个哈希表:
    • charToWord 用于存储 pattern 中的每个字符到 words 中对应单词的映射关系。
    • wordToChar 用于存储 words 中的每个单词到 pattern 中对应字符的映射关系。
  3. 遍历 pattern 中的每个字符及其对应的单词:
    • 如果当前字符已经在 charToWord 中有映射关系,但映射的单词与当前单词不一致,则返回 false
    • 如果当前单词已经在 wordToChar 中有映射关系,但映射的字符与当前字符不一致,也返回 false
    • 如果不存在不一致的情况,则建立字符与单词的双向映射关系。
  4. 如果所有字符和单词都成功建立了双向映射,并且没有冲突,则返回 true

代码的时间复杂度:

  • 时间复杂度为 O(n),其中 n 为模式字符串的长度或单词数组的长度。每个字符和单词的映射操作都是常数时间的哈希表查找操作,所以整体复杂度为线性。

通过双向映射保证了字符和单词之间的双射关系,可以确保模式与字符串的对应关系是唯一且一致的。

java 实现

class Solution {public boolean wordPattern(String pattern, String s) {//先分割单词,根据长度是否相等进行初步判断String[] words = s.split(" ");if(words.length != pattern.length()) {return false;}Map<Character, String> charToWord = new HashMap<>();Map<String, Character> WordToChar = new HashMap<>();for(int i = 0; i < pattern.length(); ++i) {String word = words[i];if(charToWord.containsKey(pattern.charAt(i))) {if(!charToWord.get(pattern.charAt(i)).equals(word)) {return false;}}else {//之所以可以通过这一部分的代码片段进行结果判断,是因为charToWord和wordToChar是同时更新的if(WordToChar.containsKey(word)) {return false;}charToWord.put(pattern.charAt(i), word);WordToChar.put(word, pattern.charAt(i));}}return true;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com