Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
#include <cassert>
#include <climits>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
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
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 |
true
if a valid solution/segmentation is possible by segmenting at index pos false
otherwise 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 |
true
if str is present in strSet false
if str is not present in strSet int main | ( | void | ) |
Main function.
|
static |
Test implementations.
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 |
true
if s can be formed by a combination of strings present in wordDict false
otherwise