c++ solution for Replace Words


  • 0
    J
    • Define a function for split a string into words
    • Define a function for searching a prefix in a list of words, return the shortest one
    • Use a hashmap to keep track of matched rooter for words, e.g., (cattle, cat)
    class Solution {
    
    public:
         std::vector<std::string > split(std::string s){
            std::vector<std::string > result;
            std::istringstream iss(s);
            for(std::string s; iss >> s; )
                result.push_back(s);
            return result;
         }
    
        string rooter(vector<string >& dict, string word){
            int minlen=word.length();
            string root=word;
            for (int i=0;i <dict.size();i++){
                int len=dict[i].length();
                string sub_word = word.substr(0,len);
                if(sub_word==dict[i]&&len<minlen){
                    root=dict[i];
                    minlen=len;
                }
            }
            return root;
        }
    
        string replaceWords(vector<string >& dict, string sentence) {
            vector<string > words;
            //split sentence into words with boost::split (is possible), otherwise, implement one
            words=split(sentence);
            //iniatialize a hashmap for storing <word, root> pairs
            unordered_map<string, string > m;
            string replacedwords; // this is the final results to be returned
            string space=string(" ");
            for (int i=0;i<words.size();i++){
                if(m.find(words[i])==m.end()) //new rooter found
                    m[words[i]] = rooter(dict, words[i]);
                replacedwords+=m[words[i]];
                replacedwords+=space;
            }
            replacedwords.pop_back();
            return replacedwords;
        }
    };
    

Log in to reply
 

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