给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern ="abba", s ="dog cat cat dog"输出: true
示例 2:
输入:pattern ="abba", s ="dog cat cat fish"输出: false
示例 3:
输入: pattern ="aaaa", s ="dog cat cat dog"输出: false
提示:
1 <= pattern.length <= 300pattern只包含小写英文字母1 <= s.length <= 3000s只包含小写英文字母和' 's不包含 任何前导或尾随对空格s中每个单词都被 单个空格 分隔
朴素解法：
给对应的字符打上印记，使用该字符首次出现的索引位置作为印记值，使用哈希表记录。
而后，将字符串转换为对应的索引数组，如 pattern = "abbac"，转换后为 [0, 1, 1, 0, 4]。对于字符串 s 同理。
需注意，
pattern以char为key；而s则是以' '作为分割符，转换为字符串数组之后，以成员String为key。
对比两个索引数组，在所有成员一一对应的情况下，才能表示两者规律一致。
优化：
转换为索引数组方便理解，但是太浪费。
可以选择再次遍历字符串，以 key 取值对比即可。
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
s = s.split(' ')
n = len(pattern)
if n != len(s):
return False
c2str, str2c = defaultdict(), defaultdict()
for i in range(n):
k, v = pattern[i], s[i]
if k in c2str and c2str[k] != v:
return False
if v in str2c and str2c[v] != k:
return False
c2str[k], str2c[v] = v, k
return Trueclass Solution {
public boolean wordPattern(String pattern, String s) {
String[] ss = s.split(" ");
int n = pattern.length();
if (n != ss.length) {
return false;
}
Map<Character, String> c2str = new HashMap<>();
Map<String, Character> str2c = new HashMap<>();
for (int i = 0; i < n; ++i) {
char k = pattern.charAt(i);
String v = ss[i];
if (c2str.containsKey(k) && !Objects.equals(c2str.get(k), v)) {
return false;
}
if (str2c.containsKey(v) && !Objects.equals(str2c.get(v), k)) {
return false;
}
c2str.put(k, v);
str2c.put(v, k);
}
return true;
}
}function wordPattern(pattern: string, s: string): boolean {
let n = pattern.length;
let values = s.split(' ');
if (n != values.length) return false;
let table = new Array(128);
for (let i = 0; i < n; i++) {
let k = pattern.charCodeAt(i),
v = values[i];
if (!table[k]) {
if (table.includes(v)) return false;
table[k] = v;
} else {
if (table[k] != v) return false;
}
}
return true;
}function wordPattern(pattern: string, s: string): boolean {
const n = pattern.length;
const cs = s.split(' ');
if (n !== cs.length) {
return false;
}
const map1 = new Map<string, number>();
const map2 = new Map<string, number>();
for (let i = 0; i < n; i++) {
const c1 = pattern[i];
const c2 = cs[i];
if (!map1.has(c1)) {
map1.set(c1, i);
}
if (!map2.has(c2)) {
map2.set(c2, i);
}
if (map1.get(c1) !== map2.get(c2)) {
return false;
}
}
return true;
}class Solution {
public:
bool wordPattern(string pattern, string s) {
istringstream is(s);
vector<string> ss;
while (is >> s) ss.push_back(s);
int n = pattern.size();
if (n != ss.size()) return false;
unordered_map<char, string> c2str;
unordered_map<string, char> str2c;
for (int i = 0; i < n; ++i) {
char k = pattern[i];
string v = ss[i];
if (c2str.count(k) && c2str[k] != v) return false;
if (str2c.count(v) && str2c[v] != k) return false;
c2str[k] = v;
str2c[v] = k;
}
return true;
}
};func wordPattern(pattern string, s string) bool {
ss := strings.Split(s, " ")
n := len(pattern)
if n != len(ss) {
return false
}
c2str := make(map[byte]string)
str2c := make(map[string]byte)
for i := 0; i < n; i++ {
k, v := pattern[i], ss[i]
if c2str[k] != "" && c2str[k] != v {
return false
}
if str2c[v] > 0 && str2c[v] != k {
return false
}
c2str[k], str2c[v] = v, k
}
return true
}use std::collections::HashMap;
impl Solution {
pub fn word_pattern(pattern: String, s: String) -> bool {
let cs1: Vec<char> = pattern.chars().collect();
let cs2: Vec<&str> = s.split_whitespace().collect();
let n = cs1.len();
if n != cs2.len() {
return false;
}
let mut map1 = HashMap::new();
let mut map2 = HashMap::new();
for i in 0..n {
let c = cs1[i];
let s = cs2[i];
if !map1.contains_key(&c) {
map1.insert(c, i);
}
if !map2.contains_key(&s) {
map2.insert(s, i);
}
if map1.get(&c) != map2.get(&s) {
return false
}
}
true
}
}