Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <map>
- #include <string>
- #include <vector>
- using namespace std;
- vector<vector<string> > _segmentString(const string& inputString, set<string>& wordList, map<string, vector<vector<string> > >& cacheMap) {
- auto targetCache = cacheMap.find(inputString);
- if (targetCache != cacheMap.end()) {
- return targetCache->second;
- }
- auto retVector = vector<vector<string> >();
- if (inputString.size() <= 1) {
- auto vec = vector<string>();
- vec.push_back(inputString);
- retVector.push_back(vec);
- } else {
- for (int i = 1; i <= inputString.size(); i++) {
- auto frontSubString = inputString.substr(0, i);
- if (wordList.find(frontSubString) != wordList.end()) {
- auto backSubString = inputString.substr(i, inputString.size());
- if (backSubString.size()) {
- auto backSegments = _segmentString(backSubString, wordList, cacheMap);
- for (auto iter = backSegments.begin(); iter != backSegments.end(); ++iter) {
- auto vec = vector<string>(*iter);
- vec.insert(vec.begin(), frontSubString);
- retVector.push_back(vec);
- }
- } else {
- auto vec = vector<string>();
- vec.push_back(frontSubString);
- retVector.push_back(vec);
- }
- }
- }
- }
- cacheMap.insert(pair<string, vector<vector<string> > >(inputString, retVector));
- return retVector;
- }
- vector<vector<string> > segmentString(const string& inputString, set<string>& wordList) {
- auto cacheMap = map<string, vector<vector<string> > >();
- return _segmentString(inputString, wordList, cacheMap);
- }
- int main() {
- string aaa = "nimenhao";
- //nimenhao
- auto wordlist = set<string>();
- for (char c = 'a'; c <= 'z'; ++c) {
- wordlist.insert(string(1, c));
- }
- string l[] = {"ni", "me", "men", "ha", "hao", "ao"};
- for (auto i = 0; i < sizeof(l) / sizeof(string); i++) {
- wordlist.insert(l[i]);
- }
- auto segResult = segmentString(aaa, wordlist);
- for (auto iter = segResult.begin(); iter != segResult.end(); ++iter) {
- auto& row = *iter;
- for (auto innerIter = row.begin(); innerIter != row.end(); ++innerIter) {
- if (innerIter != row.begin()) {
- cout << '|';
- }
- cout << '(' << *innerIter << ')';
- }
- cout << endl;
- }
- return 0;
- }
- /*
- *
- * Result Will Be
- (n)|(i)|(m)|(e)|(n)|(h)|(a)|(o)
- (n)|(i)|(m)|(e)|(n)|(h)|(ao)
- (n)|(i)|(m)|(e)|(n)|(ha)|(o)
- (n)|(i)|(m)|(e)|(n)|(hao)
- (n)|(i)|(me)|(n)|(h)|(a)|(o)
- (n)|(i)|(me)|(n)|(h)|(ao)
- (n)|(i)|(me)|(n)|(ha)|(o)
- (n)|(i)|(me)|(n)|(hao)
- (n)|(i)|(men)|(h)|(a)|(o)
- (n)|(i)|(men)|(h)|(ao)
- (n)|(i)|(men)|(ha)|(o)
- (n)|(i)|(men)|(hao)
- (ni)|(m)|(e)|(n)|(h)|(a)|(o)
- (ni)|(m)|(e)|(n)|(h)|(ao)
- (ni)|(m)|(e)|(n)|(ha)|(o)
- (ni)|(m)|(e)|(n)|(hao)
- (ni)|(me)|(n)|(h)|(a)|(o)
- (ni)|(me)|(n)|(h)|(ao)
- (ni)|(me)|(n)|(ha)|(o)
- (ni)|(me)|(n)|(hao)
- (ni)|(men)|(h)|(a)|(o)
- (ni)|(men)|(h)|(ao)
- (ni)|(men)|(ha)|(o)
- (ni)|(men)|(hao)
- *
- * */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement