LeetCode150道面试经典题--单词规律(简单)

1.题目

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

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

2.示例

pattern="abba"

s = "cat dog dog cat"

返回 true

pattern="abba"

s = "cat pig dog cat"

返回 false

pattern="ab"

s = "cat cat"

返回 false

提示

• 1 <= pattern.length <= 300
• pattern 只包含小写英文字母
• 1 <= s.length <= 3000
• s 只包含小写英文字母和 ' '
• s 不包含 任何前导或尾随对空格
• s 中每个单词都被 单个空格 分隔

---

3.思路

哈希表：

        首先看到映射相关问题就得联想到哈希表，然后先分析特殊情况，比如s为空或者s里面的字母个数和pattern的个数不匹配则直接返回false，否则正常情况下，先将s通过spilt方法进行切割后，在遍历s情况下，不存在的键值对应的映射就存入哈希表中，存在的就比较是否相等即可。

如果不了解哈希表则可以通过以下内容了解相关知识

Java类集框架（二）_Alphamilk的博客-CSDN博客

4.代码

LeetCode代码：

使用时间优先代码：

class Solution {public boolean wordPattern(String pattern, String s) {
//        判断两种特殊情况if (s.length() ==0){return false;}String ss[] = s.split(" ");if (ss.length != pattern.length()){return false;}//        正常情况HashMap<Character,String> map = new HashMap<>();for (int i= 0;i<pattern.length();i++){if (!map.containsKey(pattern.charAt(i))){if (map.containsValue(ss[i])){return false;}map.put(pattern.charAt(i),ss[i]);}else {if (!map.get(pattern.charAt(i)).equals(ss[i])){return false;}}}return true;}
}

还有一种做法是通过构造两个哈希表实现，内存上稍微会优于该算法，但是时间上会慢一些。

案例详细代码：

package LeetCode14;import java.util.Arrays;
import java.util.HashMap;public class javaDemo {public static void main(String[] args) {String pattern = "abbc";String s = "";boolean flag = true;//        判断两种特殊情况
//        当s为空if (s.length() ==0){flag = false;}
//        当ss中单词个数与pattern个数不匹配情况String ss[] = s.split(" ");if (ss.length != pattern.length()){flag = false;}//        正常情况HashMap<Character,String> map = new HashMap<>();
//        遍历整个patternfor (int i= 0;i<pattern.length();i++){
//            判断是否存在键值if (!map.containsKey(pattern.charAt(i))){
//                判断值是否已经对应其他键值if (map.containsValue(ss[i])){flag = false;break;}
//              不满足前面条件的话就正常放入map.put(pattern.charAt(i),ss[i]);}else {
//                如果有存在的键，则进行比较if (!map.get(pattern.charAt(i)).equals(ss[i])){flag = false;break;}}}
//        输出flagSystem.out.println(flag);}
}

---

会了？试试挑战下一题！♪（＾∀＾●）ﾉｼ （●´∀｀）♪ 

LeetCode150道面试经典题-- 有效的字母异位词(简单)_Alphamilk的博客-CSDN博客