#include <bits/stdc++.h>
using
namespace
std;
const
int
ALPHABET_SIZE = 26;
struct
TrieNode {
struct
TrieNode* children[ALPHABET_SIZE];
bool
isEndOfWord;
};
struct
TrieNode* getNode(
void
)
{
struct
TrieNode* pNode =
new
TrieNode;
pNode->isEndOfWord =
false
;
for
(
int
i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
return
pNode;
}
void
insert(
struct
TrieNode* root, string key)
{
struct
TrieNode* pCrawl = root;
for
(
int
i = 0; i < key.length(); i++) {
int
index = key[i] -
'a'
;
if
(!pCrawl->children[index])
pCrawl->children[index] = getNode();
pCrawl = pCrawl->children[index];
}
pCrawl->isEndOfWord =
true
;
}
void
minWordBreak(
struct
TrieNode* root,
string key,
int
start,
int
* min_Break,
int
level = 0)
{
struct
TrieNode* pCrawl = root;
if
(start == key.length()) {
*min_Break = min(*min_Break, level - 1);
return
;
}
int
minBreak = 0;
for
(
int
i = start; i < key.length(); i++) {
int
index = key[i] -
'a'
;
if
(!pCrawl->children[index])
return
;
if
(pCrawl->children[index]->isEndOfWord)
minWordBreak(root, key, i + 1,
min_Break, level + 1);
pCrawl = pCrawl->children[index];
}
}
int
main()
{
string dictionary[] = {
"Cat"
,
"Mat"
,
"Ca"
,
"Ma"
,
"at"
,
"C"
,
"Dog"
,
"og"
,
"Do"
};
int
n =
sizeof
(dictionary) /
sizeof
(dictionary[0]);
struct
TrieNode* root = getNode();
for
(
int
i = 0; i < n; i++)
insert(root, dictionary[i]);
int
min_Break = INT_MAX;
minWordBreak(root,
"CatMatat"
, 0, &min_Break, 0);
cout << min_Break << endl;
return
0;
}