forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 1
/
word-pattern.py
69 lines (60 loc) · 1.73 KB
/
word-pattern.py
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# Time: O(n)
# Space: O(c), c is unique count of pattern
from itertools import izip # Generator version of zip.
class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
if len(pattern) != self.wordCount(str):
return False
w2p, p2w = {}, {}
for p, w in izip(pattern, self.wordGenerator(str)):
if w not in w2p and p not in p2w:
# Build mapping. Space: O(c)
w2p[w] = p
p2w[p] = w
elif w not in w2p or w2p[w] != p:
# Contradict mapping.
return False
return True
def wordCount(self, str):
cnt = 1 if str else 0
for c in str:
if c == ' ':
cnt += 1
return cnt
# Generate a word at a time without saving all the words.
def wordGenerator(self, str):
w = ""
for c in str:
if c == ' ':
yield w
w = ""
else:
w += c
yield w
# Time: O(n)
# Space: O(n)
class Solution2(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
words = str.split() # Space: O(n)
if len(pattern) != len(words):
return False
w2p, p2w = {}, {}
for p, w in izip(pattern, words):
if w not in w2p and p not in p2w:
# Build mapping. Space: O(c)
w2p[w] = p
p2w[p] = w
elif w not in w2p or w2p[w] != p:
# Contradict mapping.
return False
return True