word_break.cpp

Go to the documentation of this file.

 
#include <cassert>
#include <climits>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

namespace dynamic_programming {

namespace word_break {

bool exists(const std::string &str,
            const std::unordered_set<std::string> &strSet) {
    return strSet.find(str) != strSet.end();
}

bool check(const std::string &s, const std::unordered_set<std::string> &strSet,
           int pos, std::vector<int> *dp) {
    if (pos == s.length()) {
        // if we have reached till the end of the string, means we have
        // segmented throughout correctly hence we have a solution, thus
        // returning true
        return true;
    }
 
    if (dp->at(pos) != INT_MAX) {
        // if dp[pos] is not INT_MAX, means we must have saved a solution
        // for the position pos; then return if the solution at pos is true
        // or not
        return dp->at(pos) == 1;
    }
 
    std::string wordTillNow =
        "";  // string to save the prefixes of word till different positons
 
    for (int i = pos; i < s.length(); i++) {
        // Loop starting from pos to end, to check valid set of
        // segmentations if any
        wordTillNow +=
            std::string(1, s[i]);  // storing the prefix till the position i
 
        // if the prefix till current position is present in the dictionary
        // and the remaining substring can also be segmented legally, then
        // set solution at position pos in the memo, and return true
        if (exists(wordTillNow, strSet) && check(s, strSet, i + 1, dp)) {
            dp->at(pos) = 1;
            return true;
        }
    }
    // if function has still not returned, then there must be no legal
    // segmentation possible after segmenting at pos
    dp->at(pos) = 0;  // so set solution at pos as false
    return false;     // and return no solution at position pos
}

bool wordBreak(const std::string &s, const std::vector<std::string> &wordDict) {
    // unordered set to store words in the dictionary for constant time
    // search
    std::unordered_set<std::string> strSet;
    for (const auto &s : wordDict) {
        strSet.insert(s);
    }
    // a vector to be used for memoization, whose value at index i will
    // tell if the string s can be segmented (correctly) at position i.
    // initializing it with INT_MAX (which will denote no solution)
    std::vector<int> dp(s.length(), INT_MAX);
 
    // calling check method with position = 0, to check from left
    // from where can be start segmenting the complete string in correct
    // manner
    return check(s, strSet, 0, &dp);
}
 
}  // namespace word_break
}  // namespace dynamic_programming

static void test() {
    // the complete string
    const std::string s = "applepenapple";
    // the dictionary to be used
    const std::vector<std::string> wordDict = {"apple", "pen"};
 
    assert(dynamic_programming::word_break::wordBreak(s, wordDict));
 
    // should return true, as applepenapple can be segmented as apple + pen +
    // apple
    std::cout << dynamic_programming::word_break::wordBreak(s, wordDict)
              << std::endl;
    std::cout << "Test implementation passed!\n";
}

int main() {
    test();  // call the test function :)
 
    // the complete string
    const std::string s = "applepenapple";
    // the dictionary to be used
    const std::vector<std::string> wordDict = {"apple", "pen"};
 
    // should return true, as applepenapple can be segmented as apple + pen +
    // apple
    std::cout << dynamic_programming::word_break::wordBreak(s, wordDict)
              << std::endl;
}