leetcode139-word-break_trie_and_dfs.cpp

#include<vector>
#include<algorithm>
#include<iostream>
#include<bits/stdc++.h>
usingnamespacestd;

structTrieNode {
 TrieNode* next[26];
bool isEnd;
TrieNode()
 {
for (int i = 0; i < 26; i++)
 next[i] = nullptr;
 isEnd = false;
 }
};
classSolution {
 TrieNode* root;
int failMemo[301]; // 记录dfs中失败时对应的s中的index
public:
boolwordBreak(string s, vector<string>& wordDict) {
 root = newTrieNode();
// 建树
for (auto& word : wordDict)
 {
 TrieNode* p = root;
for (auto& ch : word)
 {
if (p->next[ch - 'a'] == nullptr)
 p->next[ch - 'a'] = newTrieNode();
 p = p->next[ch - 'a']; 
 }
 p->isEnd = true; 
 }
returndfs(s, 0);
 }
booldfs(string& s, int startPos)
 {
if (failMemo[startPos] == 1) returnfalse; 
if (startPos == s.size()) returntrue;
 TrieNode* p = root; 
for (int i = startPos; i < s.size(); i++)
 {
if (p->next[s[i] - 'a'] != nullptr)
 {
 p = p->next[s[i] - 'a'];
if (p->isEnd == true && dfs(s, i+1))
returntrue; 
 }
elsebreak; 
 }
 failMemo[startPos] = 1;
returnfalse;
 }
};

// Test
intmain()
{
 Solution sol;
 string s = "applepenapple";
 vector<string> wordDict = {"apple", "pen"};
// 预期输出: true
auto res = sol.wordBreak(s, wordDict);
 cout << (res == true ? "true" : "false");

return0;
}