题目地址: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;
}
发现评论区大佬的做法还是有一点点算法的思想的,对比之下我只是单纯的考虑了内存(而且内存还比人家高)没有考虑性能
又是垃圾的一天啊