290. Word Pattern

  • 32.5%

https://leetcode.com/problems/word-pattern/#/description

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.

Examples:

  1. pattern = “abba”, str = “dog cat cat dog” should return true.
  2. pattern = “abba”, str = “dog cat cat fish” should return false.
  3. pattern = “aaaa”, str = “dog cat cat dog” should return false.
  4. pattern = “abba”, str = “dog dog dog dog” should return false.

Notes:

You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.


https://discuss.leetcode.com/topic/26376/short-c-read-words-on-the-fly

Short C++, read words on the fly

I think all previous C++ solutions read all words into a vector at the start. Here I read them on the fly.

1
2
3
4
5
6
7
8
9
10
11
12
bool wordPattern(string pattern, string str) {
map<char, int> p2i;
map<string, int> w2i;
istringstream in(str);
int i = 0, n = pattern.size();
for (string word; in >> word; ++i) {
if (i == n || p2i[pattern[i]] != w2i[word])
return false;
p2i[pattern[i]] = w2i[word] = i + 1;
}
return i == n;
}

https://discuss.leetcode.com/topic/26316/short-in-python

Short in Python

This problem is pretty much equivalent to Isomorphic Strings. Let me reuse two old solutions.

From here:

1
2
3
4
def wordPattern(self, pattern, str):
s = pattern
t = str.split()
return map(s.find, s) == map(t.index, t)

Improved version also from there:

1
2
3
def wordPattern(self, pattern, str):
f = lambda s: map({}.setdefault, s, range(len(s)))
return f(pattern) == f(str.split())

From here:

1
2
3
4
def wordPattern(self, pattern, str):
s = pattern
t = str.split()
return len(set(zip(s, t))) == len(set(s)) == len(set(t)) and len(s) == len(t)

Thanks to zhang38 for pointing out the need to check len(s) == len(t) here.


https://discuss.leetcode.com/topic/26313/0ms-c-solution-using-istringstream-and-double-maps

0ms C++ solution using istringstream and double maps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool wordPattern(string pattern, string str) {
istringstream strcin(str);
string s;
vector<string> vs;
while(strcin >> s) vs.push_back(s);
if (pattern.size() != vs.size()) return false;
map<string, char> s2c;
map<char, string> c2s;
for (int i = 0; i < vs.size(); ++i) {
if (s2c[vs[i]] == 0 && c2s[pattern[i]] == "") {
s2c[vs[i]] = pattern[i];
c2s[pattern[i]] = vs[i];
continue;
}
if (s2c[vs[i]] != pattern[i]) return false;
}
return true;
}

https://discuss.leetcode.com/topic/36612/my-solution-in-python

My solution in python

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
x = str.split(' ')
lsp = len(set(pattern))
lsx = len(set(x))
return len(x)==len(pattern) and lsx==lsp and lsp== len(set(zip(pattern, x)))

please point out if there’s anything i should improve


2ms, 51.78%, October 18, 2016

https://discuss.leetcode.com/topic/26339/8-lines-simple-java

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public boolean wordPattern(String pattern, String str) {
String[] words = str.split(" ");
if(words.length!=pattern.length())
return false;
Map index = new HashMap();
for(Integer i=0; i<words.length; ++i)
if(index.put(pattern.charAt(i), i) != index.put(words[i], i))
return false;
return true;
}
}
谢谢你,可爱的朋友。