Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
- You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
Examples:
- pattern = "abba", str = "dog cat cat dog" should return true.
- pattern = "abba", str = "dog cat cat fish" should return false.
- pattern = "aaaa", str = "dog cat cat dog" should return false.
- pattern = "abba", str = "dog dog dog dog" should return false.
C Solution:
bool isequal(char *a, char *b, int len) {
int i;
for (i = 0; i < len; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
struct He {
char *str;
int len;
struct He *next;
};
struct Ht {
int size;
struct He **list;
};
bool find(struct Ht *ht, char *str, int len) {
unsigned ind = 0, t = 1;
int i;
for (i = 0; i < len; i++) {
ind += str[i] * t;
t *= 26;
}
ind %= ht->size;
struct He *p = ht->list[ind];
while (p) {
if (p->len == len && isequal(p->str, str, len)) return true;
p = p->next;
}
return false;
}
void insert(struct Ht *ht, char *str, int len) {
unsigned ind = 0, t = 1;
int i;
for (i = 0; i < len; i++) {
ind += str[i] * t;
t *= 26;
}
ind %= ht->size;
struct He *p = malloc(sizeof(struct He));
p->str = str;
p->len = len;
p->next = ht->list[ind];
ht->list[ind] = p;
}
bool wordPattern(char* pattern, char* str) {
char *ctos[26] = {0};
int *ctosLen[26] = {0};
struct Ht tmp, *ht = &tmp;
ht->size = 1000;
ht->list = calloc(ht->size, sizeof(struct He *));
char *p;
for (; *pattern; pattern++) {
for (p = str; *p && *p != ' '; p++);
if (ctos[*pattern - 'a'] && !isequal(ctos[*pattern - 'a'], str, p - str)) return false;
if (!ctos[*pattern - 'a']) {
if (find(ht, str, p - str)) return false;
ctos[*pattern - 'a'] = str;
ctosLen[*pattern - 'a'] = p - str;
insert(ht, str, p - str);
}
if (!*p) {
if (*(pattern + 1)) return false;
return true;
}
str = p + 1;
}
if (!*str) return true;
return false;
}
Python Solution 1:
class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
dp = {}
ds = {}
strl = str.split()
if len(pattern) != len(strl): return False
for i, val in enumerate(pattern):
if val not in dp and strl[i] not in ds:
dp[val] = i
ds[strl[i]] = i
continue
if val in dp and strl[i] in ds and dp[val] == ds[strl[i]]: continue
return False
return True
Python Solution 2:
class Solution(object):
def wordPattern(self, pattern, str):
s = pattern
t = str.split()
return map(s.find, s) == map(t.index, t)
Summary:
- Using C to solve problems related to HashTable and string is painful.
- What this problem need is a dictionary and a set.
- Fortunately, array could perform the dictionary, so I only need to implement a set HashTable.
- 0ms, 6.67%
- If I use python or java or c++ to solve the problem, I could split str first and then use two dictionary to compare. The code could be concise, but not as efficient as c solution.
- Same as the above problem 205. Isomorphic Strings.
- Python Solution 2 is beautiful.
LeetCode: 290. Word Pattern
近期评论