Skip to content

Instantly share code, notes, and snippets.

@madrugado
Created October 22, 2015 21:18
Show Gist options
  • Save madrugado/6f808b655b9107be0658 to your computer and use it in GitHub Desktop.
Save madrugado/6f808b655b9107be0658 to your computer and use it in GitHub Desktop.
The problem solved by this code is: we need to find a longest chain of substrings, where substring produced from string by dropping of one letter. The input reading is omitted.
#include <iostream>
#import <vector>
#import <string>
#import <set>
#import <algorithm>
#import <map>
using namespace std;
int main() {
vector<string> w;
sort(w.begin(), w.end(), [](const string& first, const string& second) {return first.size() < second.size();});
set<string> s(w.begin(), w.end());
map<string, set<string> > words;
for (auto&& str: w) {
for (unsigned j=0; j < str.length(); ++j) {
string temp = str.substr(0, j) + str.substr(j + 1);
if (s.find(temp) != s.end()) {
words[str].insert(temp);
}
}
}
map<string, unsigned > maxlen;
for (auto&& str: w) {
unsigned maxl = 0;
for (auto&&word: words[str]) {
if (maxl < maxlen[word] + 1) {
maxl = maxlen[word] + 1;
}
}
if (maxl != 0) {
maxlen[str] = maxl;
} else {
maxlen[str] = 0;
}
}
auto pr = std::max_element(maxlen.begin(), maxlen.end(),
[](const pair<string, unsigned>& p1, const pair<string, unsigned>& p2) {
return p1.second < p2.second; });
cout << pr->first;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment