所用数据结构
哈希表
核心方法
判断字符串pattern 和字符串s 是否存在一对一的映射关系，按照题意，双向连接的对应规律。
思路以及实现步骤
1.字符串s带有空格，因此需要转换成字符数组进行更方便的操作，将字符串s拆分成单词列表之后，就可以很方便地通过索引访问每个单词，这样在后续的遍历和比较过程中会更加的高效。因此首先将字符串s按照空格分割成单词数组list。
String[] list = s.split(" ");2.如果list的长度和pattern的长度不相等，直接说明二者无法建立映射关系，直接返回false即可。
if(list.length != pattern.length()){
return false;
}3.创建两个哈希表 c2s c2s 分别用于存储字符到单词和单词到字符的映射关系
HashMap<Character,String> c2s = new HashMap<Character,String>();
HashMap<String,Character> s2c = new HashMap<String,Character>();4. 遍历list数组和字符串pattern，检查当前字符和单词是否与之前建立的映射关系一致，不一致直接返回false 每次遍历都把当前字符和单词的映射关系存储到两个HashMap中
for(int i = 0;i<list.length;i++){
if(c2s.containsKey(pattern.charAt(i))){
if( !c2s.get(pattern.charAt(i)).equals(list[i])){
return false;
}
}
if(s2c.containsKey(list[i])){
if( !s2c.get(list[i]).equals(pattern.charAt(i))){
return false;
}
}
c2s.put(pattern.charAt(i),list[i]);
s2c.put(list[i],pattern.charAt(i));
}6.如果遍历完成说明存在单词和字符的双向映射关系，返回true，否则直接在循环中返回false
下面是完整的代码
class Solution {
public boolean wordPattern(String pattern, String s) {
HashMap<Character,String> c2s = new HashMap<Character,String>();
HashMap<String,Character> s2c = new HashMap<String,Character>();
String[] list = s.split(" ");
if(list.length != pattern.length()){
return false;
}
for(int i = 0;i<list.length;i++){
if(c2s.containsKey(pattern.charAt(i))){
if( !c2s.get(pattern.charAt(i)).equals(list[i])){
return false;
}
}
if(s2c.containsKey(list[i])){
if( !s2c.get(list[i]).equals(pattern.charAt(i))){
return false;
}
}
c2s.put(pattern.charAt(i),list[i]);
s2c.put(list[i],pattern.charAt(i));
}
return true;
}
}下面模拟一下代码的执行过程，模拟的是成功匹配的过程
pattern = "abba"
s = "dog cat cat dog"
代码的执行过程如下:
- 首先我们将字符串
s按照空格分割成单词数组list = ["dog", "cat", "cat", "dog"]。 - 由于
list的长度为 4 与pattern的长度为 4 相等,所以可以继续执行后续步骤。 - 创建两个 HashMap
c2s和s2c。 - 开始遍历
pattern和list。
第一次循环:
pattern.charAt(0) = 'a'list[0] = "dog"- 由于
c2s中不存在 'a' 这个键,所以将 ('a', "dog") 添加到c2s中。 - 由于
s2c中不存在 "dog" 这个值,所以将 ("dog", 'a') 添加到s2c中。
第二次循环:
pattern.charAt(1) = 'b'list[1] = "cat"- 由于
c2s中不存在 'b' 这个键,所以将 ('b', "cat") 添加到c2s中。 - 由于
s2c中不存在 "cat" 这个值,所以将 ("cat", 'b') 添加到s2c中。
第三次循环:
pattern.charAt(2) = 'b'list[2] = "cat"- 由于
c2s中已经存在 'b' 这个键,且对应的值为 "cat",所以检查是否与当前值 "cat" 相同,结果为 true。 - 由于
s2c中已经存在 "cat" 这个值,且对应的字符为 'b',所以检查是否与当前字符 'b' 相同,结果为 true。
第四次循环:
pattern.charAt(3) = 'a'list[3] = "dog"- 由于
c2s中已经存在 'a' 这个键,且对应的值为 "dog",所以检查是否与当前值 "dog" 相同,结果为 true。 - 由于
s2c中已经存在 "dog" 这个值,且对应的字符为 'a',所以检查是否与当前字符 'a' 相同,结果为 true。
经过上述步骤,我们发现 pattern 和 s 的映射关系是一致的,所以最终返回 true。
模拟的是失败匹配的过程
pattern = "abba"
s = "dog cat cat fish"
代码的执行过程如下:
- 首先我们将字符串
s按照空格分割成单词数组list = ["dog", "cat", "cat", "fish"]。 - 由于
list的长度为 4 与pattern的长度为 4 相等,所以可以继续执行后续步骤。 - 创建两个 HashMap
c2s和s2c。 - 开始遍历
pattern和list。
第一次循环:
pattern.charAt(0) = 'a'list[0] = "dog"- 由于
c2s中不存在 'a' 这个键,所以将 ('a', "dog") 添加到c2s中。 - 由于
s2c中不存在 "dog" 这个值,所以将 ("dog", 'a') 添加到s2c中。
第二次循环:
pattern.charAt(1) = 'b'list[1] = "cat"- 由于
c2s中不存在 'b' 这个键,所以将 ('b', "cat") 添加到c2s中。 - 由于
s2c中不存在 "cat" 这个值,所以将 ("cat", 'b') 添加到s2c中。
第三次循环:
pattern.charAt(2) = 'b'list[2] = "cat"- 由于
c2s中已经存在 'b' 这个键,且对应的值为 "cat",所以检查是否与当前值 "cat" 相同,结果为 true。 - 由于
s2c中已经存在 "cat" 这个值,且对应的字符为 'b',所以检查是否与当前字符 'b' 相同,结果为 true。
第四次循环:
pattern.charAt(3) = 'a'list[3] = "fish"- 由于
c2s中已经存在 'a' 这个键,且对应的值为 "dog",所以检查是否与当前值 "fish" 相同,结果为 false。因此返回false。
