题目
给定一种规律 pattern
和一个字符串 s
,判断
s
是否遵循相同的规律。
这里的 遵循 指完全匹配,例如, pattern
里的每个字母和字符串 s
中的每个非空单词之间存在着双向连接的对应规律。
示例1:
1 2
| 输入: pattern = "abba", s = "dog cat cat dog" 输出: true
|
示例 2:
1 2
| 输入:pattern = "abba", s = "dog cat cat fish" 输出: false
|
示例 3:
1 2
| 输入: pattern = "aaaa", s = "dog cat cat dog" 输出: false
|
提示:
1 <= pattern.length <= 300
pattern
只包含小写英文字母
1 <= s.length <= 3000
s
只包含小写英文字母和 ' '
s
不包含 任何前导或尾随对空格
s
中每个单词都被 单个空格 分隔
题解
这题其实和205
同构字符串很像的,需要建立pattern->s
和s->pattern
的映射。这里我们要清楚pattern的长度和s单词的个数应该是对应的,不然要return false
。然后我们挨个遍历就好了,遇到没有出现过的加入哈希表,如果出现过但是不相等return false
,如果有一个没查到说明对不上return false
。最后是91%时间复杂度,还可以~(●ˇ∀ˇ●)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| class Solution { public boolean wordPattern(String pattern, String s) { String[] sArray = s.split(" "); HashMap<Character, String> p2s = new HashMap<>(); HashMap<String, Character> s2p = new HashMap<>(); if (pattern.length() != sArray.length) { return false; } for (int i = 0; i < pattern.length(); i++) { String valueString = p2s.get(pattern.charAt(i)); Character valueChar = s2p.get(sArray[i]); if (valueString != null && valueChar != null) { if (!valueString.equals(sArray[i]) || !valueChar.equals(pattern.charAt(i))) { return false; } } else if ((valueChar == null && valueString != null) || (valueChar != null && valueString == null)) { return false; } else { p2s.put(pattern.charAt(i), sArray[i]); s2p.put(sArray[i], pattern.charAt(i)); } } return true; } }
|