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:

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.

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.

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:

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:

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

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

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

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;
    }
}