Short C++, read words on the fly


  • 88

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

  • 5
    H
     bool wordPattern(string pattern, string str) {
        stringstream ss(str);
        string s;
        int idx = 0, size = pattern.size();
        unordered_map<char, string> map;
        unordered_set<string> set;
        
        while(getline(ss,s,' ') && idx <= size) {
            if(map.find(pattern[idx]) != map.end() && map[pattern[idx]] != s)
                return false;
            if(map.find(pattern[idx]) == map.end() && set.count(s) > 0)
                return false;
            map[pattern[idx++]] = s;
            set.insert(s);
        }
        return idx == size;
    }
    

    On the fly too, using 1 hash_set, 1 hash_map, and 1 index.


  • 3

    The ? true : false burns my eyes :-P
    I guess I'll never understand why people do that. Can you tell why you do?

    You can also use map.count, makes it shorter and faster.


  • 0
    H
    This post is deleted!

  • 0

    Really nice i + 1: I guess you do this because you want to avoid 0 appearing as values since map will assign default 0 values once we index some non-existed keys?

    BTW, I really want to know how could you know so many built-ins, like istringstream in this problem and make such a nice use of them :-)


  • 0

    Yes, to avoid the otherwise double meaning of 0. Alternatively I considered counting backwards from n to 1, but I didn't really like it:

    bool wordPattern(string pattern, string str) {
        map<char, int> p2i;
        map<string, int> w2i;
        istringstream in(str);
        int n = pattern.size(), i = n;
        for (string word; in >> word; --i) {
            if (!i || p2i[pattern[n-i]] != w2i[word])
                return false;
            p2i[pattern[n-i]] = w2i[word] = i;
        }
        return !i;
    }
    

    Hmm, istringstream is really one of the basics and I think every C++ coder should know it, no?


  • 0
    S

    In the end ,just return idx==size; will be ok.


  • 0
    C

    The way to write for loop is really nice, as always!


  • 0
    S

    I appreciate the nice solution.


  • 0
    B

    In Line 7, why use i == n ? I tried to take out it and it also worked. thanks.


  • 0

    @bikeboy106 Because i can actually become n, and then without that check, I'd access pattern[n], possibly even pattern[n+1] and more, which is invalid and thus dangerous. Might even crash.


  • 0
    J

    what if pattern.size() > int_max...oh I know it's impossible...


  • 0

    I guess if that could happen, I'd use long or auto :)


  • 3
    W

    For better performance, map can be replace by unordered_map. And even we can use array (int p2i[26] {}) to represent the p2i. (It's ok if any character is allowed in the pattern string. Just use int p2i[CHAR_MAX]{} instead)

    bool wordPattern(string pattern, string str) {
        int p2i[26] {};
        unordered_map<string, int> w2i;
        
        istringstream in(str);
        int i = 0, n = pattern.size();
        for (string word; in >> word && i < n; ++i) {
            if (p2i[pattern[i] - 'a'] != w2i[word])
                return false;
            p2i[pattern[i] - 'a'] = w2i[word] = i + 1;
        }
        
        return i == n;
    }

  • 0
    W

    @wfxr It seems Leetcode added some new tests. You solution cannot work now.


  • 0
    D

    using unordered_map is better efficient


  • 0
    J

    Insert method is faster than find method.

    class Solution {
    public:
        bool wordPattern(string pattern, string str) {
            unordered_map<char, int> p_table;
            unordered_map<string, int> s_table;
    
            istringstream in(str);
            int i = 0;
            for (string word; in >> word; ++i) {
                auto p_res = p_table.insert({pattern[i], p_table.size()});
                auto s_res = s_table.insert({word, s_table.size()});
                if (p_res.first->second != s_res.first->second) {
                    return false;
                }
            }
            return i == pattern.size();
        }
    };
    
    

  • 0
    C

    Using (i+1) as a map from char/string to int. Very impressive!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.