Question

How to check whether a string can be segmented into a sequence of words from a dictionary in C++

Answer 1

#include <unordered_set>
#include <iostream>
#include <vector>

bool wordBreak(std::string s, std::unordered_set<std::string>& dict) {
    int slen = s.length();
    std::vector<bool> result(slen + 1, false);
    result[0] = true; // empty string is always segmentable

    for (int i = 1; i <= slen; i++) {
        for (int j = 0; j < i; j++) {
            if (result[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                result[i] = true;
                break;
            }
        }
    }

    return result[slen];
}

int main() {
    std::unordered_set<std::string> dict = {"future", "depends", "the", "on", 
                                            "your", "dreams", "start", "today"};
    std::string s = "futuredependsonyourdreams";

    if (wordBreak(s, dict))
        std::cout << "The string can be segmented\n";
    else
        std::cout << "The string cannot be segmented\n";
}



/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <string>
#include <vector>
 
#define DICTLEN 8
 
bool isInDict(const std::string& word, const std::vector<std::string>& dict) {
    for (const auto& d : dict) {
        if (d == word) {
            return true;
        }
    }
     
    return false;
}
 
bool wordBreak(const std::string& str, const std::vector<std::string>& dict, std::string result = "") {
    int len = str.length();
     
    for (int i = 1; i <= len; ++i) {
        std::string prefix = str.substr(0, i);
        if (isInDict(prefix, dict)) {
            if (i == len) {
                result += prefix;
                return true;
            }
            if (wordBreak(str.substr(i), dict, result + prefix + " ")) {
                return true;
            }
        }
    }
     
    return false;
}
 
int main() {
    std::vector<std::string> dict = {"future", "depends", "the", "on", "your", 
                                     "dreams", "start", "today"};
    std::string s = "futuredependsonyourdreams";
 
    if (wordBreak(s, dict))
        std::cout << "The string can be segmented\n";
    else
        std::cout << "The string cannot be segmented\n";
}
  
  
  
/*
run:
  
The string can be segmented
  
*/

 

70+ SQL courses for beginners and professionals

Answer 3

#include <iostream>
#include <vector>

int isInDict(std::string word, std::vector<std::string> dict) {    
    int dictsize = dict.size();
    
    for (int i = 0; i < dictsize; i++) {
        if (dict[i].compare(word) == 0) {
             return true;
        }
    }
    
    return false;
}

void wordBreak(std::string str, int strsize, std::string result, std::vector<std::string> dict) {
    for (int i = 1; i <= strsize; i++) {
        std::string subStr = str.substr(0, i);    
      
        if (isInDict(subStr, dict)) {       
            if (i == strsize) {
                result += subStr; 
                std::cout << result << std::endl;
                return;
            }
            wordBreak(str.substr(i, strsize - i), strsize - i, result + subStr + " ", dict);    
      }
   }
}

int main() {
    std::string str = "butterflyplaybasketballwithbags";
    std::vector<std::string> dict =  {"butterfly", "basketball", "bagpiper", "and", "play", 
                                      "with", "butter", "fly", "basket", "ball", "bags"};
                                      
    wordBreak(str, str.size(), "", dict);
}
 
 
/*
run:
 
butter fly play basket ball with bags
butter fly play basketball with bags
butterfly play basket ball with bags
butterfly play basketball with bags
 
*/

 

70+ SQL courses for beginners and professionals