2023-08-04 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 4

Description

Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

 

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

 

Constraints:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

Solution

struct TrieNode {
  bool end = false;
  TrieNode *child[26] = {};
};
void insert(TrieNode *root, const string &word) {
  TrieNode *cur = root;
  for(auto c : word) {
    if(!cur->child[c - 'a']) cur->child[c - 'a'] = new TrieNode();
    cur = cur->child[c - 'a'];
  }
  cur->end = true;
}
class Solution {
  TrieNode *root;
  int len;
  vector<bool> visit;
  bool solve(const string &s, int pos) {
    TrieNode *cur = root;
    if(len == pos) return true;
    if(visit[pos]) return false;
    int start = pos;
    while(pos < len) {
      if(!cur->child[s[pos] - 'a']) {
        visit[start] = true;
        return false;
      }
      cur = cur->child[s[pos] - 'a'];
      pos += 1;
      if(cur->end && solve(s, pos)) return true;
    }
    visit[pos] = true;
    return false;
  }
public:
  bool wordBreak(string s, vector<string>& wordDict) {
    root = new TrieNode();
    len = s.length();
    visit.resize(len);
    for(const auto &word : wordDict) {
      insert(root, word);
    }
    return solve(s, 0);
  }
};

// Accepted
// 46/46 cases passed (3 ms)
// Your runtime beats 91.38 % of cpp submissions
// Your memory usage beats 54.73 % of cpp submissions (10.1 MB)
Algorithm