脚撕LeetCode(290)Easy
题目地址：https://leetcode-cn.com/problems/word-pattern/
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。 https://leetcode-cn.com/problems/word-pattern/
示例1: 输入: pattern = "abba", str = "dog cat cat dog" 输出: true 示例 2: 输入:pattern = "abba", str = "dog cat cat fish" 输出: false 示例 3: 输入: pattern = "aaaa", str = "dog cat cat dog" 输出: false 示例 4: 输入: pattern = "abba", str = "dog dog dog dog" 输出: false https://leetcode-cn.com/problems/word-pattern/
说明: 你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。 https://leetcode-cn.com/problems/word-pattern/
一、爆破法
本来打算用map的，但总感觉没有valueset很麻烦，还要自己单独维护，所以就想了这么一个办法
先将两者都切割开，如果切割后数组的长度不一样，则直接返回false（当时这一步忘记考虑吃了一个运行异常数组越界）
然后循环，model数组表示pattern中的每个字符代表s中的什么字符串，a=0，b=1以此类推
如果model中下标不存在，考虑这个单词在其他下标（懒得用遍历所以写了个set维护单词表），如果不存在则说明是新的规则和单词，如果存在则说明单词已经归属别的规则，返回false
如果s中的字符串存在model中，则对比，如果不同则返回false，如果执行完都没有返回false则返回true，说明完全匹配
运行结果如下：
36 / 36 个通过测试用例
状态：通过
执行用时: 1 ms
内存消耗: 36.4 MB
public boolean wordPatternMe(String pattern, String s) {
String[] model = new String[26];
String[] sArr = s.split(" ");
char[] charArr = pattern.toCharArray();
String value;
Set<String> valueSet = new HashSet<>();
int item;
if (sArr.length != charArr.length) return false;
for (int i = 0; i < sArr.length; i++) {
value = sArr[i];
item = charArr[i] - 'a';
if (null == model[item]) {
if (valueSet.contains(value))
return false;
valueSet.add(value);
model[item] = value;
continue;
}
if (!value.equals(model[item])) {
return false;
}
}
return true;
}二、官方双map法
跟我一开始的想法一样，用到了hashmap，但是不同的是用了双hashmap，pattern中的字符和str中的字符串互相为key,value
然后在pattern中取一个字符，接着取出str中的一个字符串，然后判断两者是否在两个map中的key存在，如果存在则拿出value比较，如果不同则返回false，如果不存在则put
最后返回true。感觉做的比我的要简单一些，时间都是1ms，内存上差别也不是很大（我用了那么多个变量，内存居然差不多，而且set就是hashmap实现的，说明一个map的空间可以用很多个数组，这个细节后面要注意）
运行结果如下：
36 / 36 个通过测试用例
状态：通过
执行用时: 1 ms
内存消耗: 36.6 MB
提交时间：3 小时前
public static boolean wordPattern(String pattern, String str) {
Map<String, Character> str2ch = new HashMap<String, Character>();
Map<Character, String> ch2str = new HashMap<Character, String>();
int m = str.length();
int i = 0;
for (int p = 0; p < pattern.length(); ++p) {
char ch = pattern.charAt(p);
if (i >= m) {
return false;
}
int j = i;
while (j < m && str.charAt(j) != ' ') {
j++;
}
String tmp = str.substring(i, j);
if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {
return false;
}
if (ch2str.containsKey(ch) && !tmp.equals(ch2str.get(ch))) {
return false;
}
str2ch.put(tmp, ch);
ch2str.put(ch, tmp);
i = j + 1;
}
return i >= m;
}接下来是评论区的大佬的方法，时间是0ms，内存也打败了70%+的用户，感觉这种方法非常值得学习
三、对比下标法
评论区大佬的办法是对比pattern中字符第一次出现的下标和S中字符串的第一次出现是否相等其实就是把key和value绑定成第一次出现的样子，如果有一方不匹配则返回false
运行结果如下：
36 / 36 个通过测试用例
状态：通过
执行用时: 0 ms
内存消耗: 36.3 MB
public boolean wordPatternBigOld(String pattern, String s) {
String[] str = s.split(" ");
if(pattern.length() != str.length){
return false;
}
for(int i = 0; i < pattern.length(); i++){
if(pattern.indexOf(pattern.charAt(i)) != getIndex(str, str[i])){
return false;
}
}
return true;
}
public int getIndex(String[] arr, String target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i].equals(target)) {
return i;
}
}
return -1;
}发现评论区大佬的做法还是有一点点算法的思想的，对比之下我只是单纯的考虑了内存（而且内存还比人家高）没有考虑性能
又是垃圾的一天啊
腾讯云开发者
