![]() |
TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
|
#include <cassert>
#include <climits>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
Go to the source code of this file.
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. |
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
Definition in file word_break.cpp.
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.
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 |
Definition at line 80 of file word_break.cpp.
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.
str | the string to be searched |
strSet | unordered set of string, that is to be looked into |
Definition at line 60 of file word_break.cpp.
int main | ( | void | ) |
Main function.
Definition at line 174 of file word_break.cpp.
|
static |
Test implementations.
Definition at line 156 of file word_break.cpp.
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.
s | the complete string to be segmented |
wordDict | a vector of words to be used as dictionary to look into |
Definition at line 131 of file word_break.cpp.