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);
}
};
Showing posts with label stringstream. Show all posts
Showing posts with label stringstream. Show all posts
Tuesday, October 10, 2017
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;
}
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";
}
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;
}
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;
}
Subscribe to:
Posts (Atom)