Showing posts with label stringstream. Show all posts
Showing posts with label stringstream. Show all posts

Tuesday, October 10, 2017

648. Replace Words

https://leetcode.com/problems/replace-words/description/
Solution 1. Trie search
class Solution {
#define NAL 26
    struct trieNode {
        trieNode* child[NAL] = {nullptr};
        bool isEnd = false;
    };
    void insert(trieNode*root, string& key) {
        trieNode* p = root;
        for(int i=0; i<key.size(); i++) {
            if(p->child[key[i]-'a'] == nullptr) {
                p->child[key[i]-'a'] = new trieNode;
            }
            p = p->child[key[i]-'a'];
            if(p->isEnd == true) return;
        }
        p->isEnd = true;
    }
    int search(trieNode*root, string& key) {
        trieNode* p = root;
        for(int i=0; i<key.size(); i++) {
            if(p->isEnd == true){ return i; }
            if(p->child[key[i]-'a'] == nullptr) return 0;
            p = p->child[key[i]-'a'];
        }
        return 0;
    }
public:
    string replaceWords(vector<string>& dict, string sentence) {
        trieNode* root = new trieNode;
        for(string &s : dict) {
            insert(root, s);
        }
        string res = "", word;
        istringstream iss(sentence);
        while(iss>>word) {
            cout<<endl;
            int len = search(root, word);
            if(len) res += " " + word.substr(0,len);
            else res += " " + word;
        }
        return res.substr(1);
    }
};

Monday, October 2, 2017

stringstream with multiple delimiters


std::stringstream stringStream(inputString);
std::string line;
while(std::getline(stringStream, line)) 
{
    std::size_t prev = 0, pos;
    while ((pos = line.find_first_of(" ';", prev)) != std::string::npos)
    {
        if (pos > prev)
            wordVector.push_back(line.substr(prev, pos-prev));
        prev = pos+1;
    }
    if (prev < line.length())
        wordVector.push_back(line.substr(prev, std::string::npos));
}

609. Find Duplicate File in System

https://leetcode.com/problems/find-duplicate-file-in-system/description/
    vector<vector<string>> findDuplicate(vector<string>& paths) {
        unordered_map<string,vector<string>> con2path;
        for(string pth : paths) {
            stringstream ss(pth);
            string item;
            getline(ss, item, ' ');
            string path = item + "/";
            while(getline(ss, item, ' ')) {
                //size_t l = item.find('(');
                //size_t r = item.find(')');
                //string fname = path + item.substr(0, l);
                //string content = item.substr(l+1, r-l);
                stringstream ssi(item);
                string fname;
                getline(ssi, fname, '(');
                fname = path + fname;
                string content;
                getline(ssi, content, ')');
                con2path[content].push_back(fname);
            }
        }
        vector<vector<string>> res;
        for(auto &x : con2path) if(x.second.size()>1) res.push_back(x.second);
        return res;
    }

Wednesday, September 27, 2017

537. Complex Number Multiplication

https://leetcode.com/problems/complex-number-multiplication/description/
Solution 1.stringstream
    string complexNumberMultiply(string a, string b) {
        int ar, ai, br, bi;
        char buff;
        stringstream ssa(a), ssb(b), res;
        ssa >> ar >> buff >> ai >> buff;
        ssb >> br >> buff >> bi >> buff;
        res << ar*br - ai*bi << "+" << ar*bi + br*ai << "i";
        return res.str();
    }
Solution 2. strtok
    string complexNumberMultiply(string a, string b) {
        string ars = strtok((char*)a.c_str(), "+i");
        string ais = strtok(NULL, "+i");
        string brs = strtok((char*)b.c_str(), "+i");
        string bis = strtok(NULL, "+i");
        long ar = stol(ars);
        long ai = stol(ais);
        long br = stol(brs);
        long bi = stol(bis);
        long re = ar*br - ai*bi;
        long im = ar*bi + ai*br;
     
        return to_string(re)+"+"+to_string(im)+"i";
    }

Tuesday, September 12, 2017

290. Word Pattern

https://leetcode.com/problems/word-pattern/description/
Solution 1.0 Read the string one by one and compare. Use stringstream the read. (0 ms)
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        stringstream ss(str);
        string item;
        int i=0, n=pattern.size();
        for(; getline(ss, item, ' ');i++) {
            if(i==n || mp[pattern[i]] != ms[item]) return false;
            mp[pattern[i]] = i+1;
            ms[item] = i+1;
        }
        return i==n;

    }
Solution 1.2 Use istringstream
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        istringstream in(str);
        int i = 0, n = pattern.size();
        for(string item; in>>item;i++) {
            if(i==n || mp[pattern[i]]!=ms[item])
                return false;
            mp[pattern[i]] = i+1;
            ms[item] = i+1;
        }
        return i==n;
    }
Solution 1.1 Convert the string to a vector<string> and compare. (3 ms)
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        stringstream ss(str);
        vector<string> s;
        string item;
        while(getline(ss, item, ' ')) {
            s.push_back(item);
        }
        if(pattern.size() != s.size()) return false;
        for(int i=0; i<s.size();i++) {
            if(!mp.count(pattern[i]) && !ms.count(s[i])) {
                mp[pattern[i]] = i+1;
                ms[s[i]] = i+1;
            }
            if(!mp.count(pattern[i]) || !ms.count(s[i])) return false;
            if(mp[pattern[i]] != ms[s[i]]) return false;
        }
        return true;
    }