word_break.cpp File Reference

Word Break Problem More...

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

Include dependency graph for word_break.cpp:

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.
namespace	word_break
	Functions for Word Break problem.

Functions
bool	dynamic_programming::word_break::exists (const std::string &str, const std::unordered_set< std::string > &strSet)
	Function that checks if the string passed in param is present in the the unordered_set passed.
bool	dynamic_programming::word_break::check (const std::string &s, const std::unordered_set< std::string > &strSet, int pos, std::vector< int > *dp)
	Function that checks if the string passed in param can be segmented from position 'pos', and then correctly go on to segment the rest of the string correctly as well to reach a solution.
bool	dynamic_programming::word_break::wordBreak (const std::string &s, const std::vector< std::string > &wordDict)
	Function that checks if the string passed in param can be segmented into the strings present in the vector. In others words, it checks if any permutation of strings in the vector can be concatenated to form the final string.
static void	test ()
	Test implementations.
int	main ()
	Main function.

Detailed Description

Word Break Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

Example 1: Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2: Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3: Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: false

Author

[Akshay Anand] (https://github.com/axayjha)

Function Documentation

check()

bool dynamic_programming::word_break::check	(	const std::string &	s,
		const std::unordered_set< std::string > &	strSet,
		int	pos,
		std::vector< int > *	dp )

Function that checks if the string passed in param can be segmented from position 'pos', and then correctly go on to segment the rest of the string correctly as well to reach a solution.

Parameters

s	the complete string to be segmented
strSet	unordered set of string, that is to be used as the reference dictionary
pos	the index value at which we will segment string and test further if it is correctly segmented at pos
dp	the vector to memoize solution for each position

Returns

true if a valid solution/segmentation is possible by segmenting at index pos

false otherwise

                                        {
    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) and 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
}

Here is the call graph for this function:

exists()

bool dynamic_programming::word_break::exists	(	const std::string &	str,
		const std::unordered_set< std::string > &	strSet )

Function that checks if the string passed in param is present in the the unordered_set passed.

Parameters

str	the string to be searched
strSet	unordered set of string, that is to be looked into

Returns

true if str is present in strSet

false if str is not present in strSet

                                                       {
    return strSet.find(str) != strSet.end();
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    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;
}

Here is the call graph for this function:

test()

static void test ( )

static

Test implementations.

Returns

void

                   {
    // 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";
}

Here is the call graph for this function:

wordBreak()

bool dynamic_programming::word_break::wordBreak	(	const std::string &	s,
		const std::vector< std::string > &	wordDict )

Function that checks if the string passed in param can be segmented into the strings present in the vector. In others words, it checks if any permutation of strings in the vector can be concatenated to form the final string.

Parameters

s	the complete string to be segmented
wordDict	a vector of words to be used as dictionary to look into

Returns

true if s can be formed by a combination of strings present in wordDict

false otherwise

                                                                         {
    // 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);
}

Here is the call graph for this function: