leetcode

0 class Trie {

1 struct Node {

2 Node *children[26] = {0};

3 } root;

4

5 public:

6 void insert(const string &s) {

7 Node *crnt = &root;

8

9 for (const char c : s) {

10 const int idx = c - 'a';

11 if (!crnt->children[idx]) crnt->children[idx] = new Node();

12 crnt = crnt->children[idx];

13 }

14 }

15

16 int find(const string &s, int start) const {

17 const Node *crnt = &root;

18 int n = 0;

19

20 for (int i = start; i < size(s); i++, n++) {

21 const int idx = s[i] - 'a';

22 if (!crnt->children[idx]) break;

23 crnt = crnt->children[idx];

24 }

25

26 return n;

27 }

28 };

29

30 class Solution {

31 public:

32 int minValidStrings(const vector<string> &words, const string &target) const {

33 static unsigned dp[5001];

34 const int n = size(target);

35 Trie trie;

36

37 for (const auto &word : words)

38 trie.insert(word);

39

40 memset(dp, 0xFF, sizeof(dp));

41 dp[0] = 0;

42

43 for (int i = 0; i < n; i++) {

44 if (dp[i] == -1) continue;

45 const int limit = trie.find(target, i);

46 for (int len = 1; len <= limit; len++) {

47 dp[i + len] = min(dp[i + len], dp[i] + 1);

48 }

49 }

50

51 return dp[n];

52 }

53 };