C++ 0ms without maps


  • 0
    A
    class Solution {
    public:
        bool wordPattern(string pattern, string str) {
            string a[26];
            int pattern_character_kind_count = 0;
            set<string> map_str;
            size_t word_begin = 0, word_end;
            for(auto c: pattern) {
                if(word_begin == string::npos) return false;
                word_end = str.find(" ", word_begin);
                string word = str.substr(word_begin, word_end - word_begin);
                if(a[c - 'a'] == "") {
                    pattern_character_kind_count++;
                    map_str.insert(word);
                    a[c - 'a'] = word;
                } else {
                    if(a[c - 'a'] != word) return false;
                }
                if (pattern_character_kind_count != map_str.size()) return false;
                word_begin = word_end + 1;
            }
            if(word_end != string::npos) return false;
            return true;
        }
    };
    

  • 0

    Very good solution, using set and string a[26] to ensure one-to-one relationship. Some comments are added to make it clearer.

    class Solution {
    public:
        bool wordPattern(string pattern, string str) {
            string a[26]; //only 26 different characters;
            int pattern_character_kind_count = 0; //how many distinct characters have been visited;
            set<string> map_str; //how many distinct words visited;
            size_t word_begin = 0, word_end;
            for(auto c: pattern) {
                if(word_begin == string::npos) return false;
                word_end = str.find(" ", word_begin);
                string word = str.substr(word_begin, word_end - word_begin);
                if(a[c - 'a'] == "") {
                    pattern_character_kind_count++;
                    map_str.insert(word); //set will only keep distinct words, in case of two characters related to the same word;
                    a[c - 'a'] = word;
                } else {
                    if(a[c - 'a'] != word) return false;
                }
                if (pattern_character_kind_count != map_str.size()) return false; //if several characters are related to the same word, return false directly;
                word_begin = word_end + 1;
            }
            if(word_end != string::npos) return false; //must the end of the word string now.
            return true;
        }
    };
    

Log in to reply
 

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