0% completed
Iterating backwards and the use of an array are unnecessary
dlflann
Jun 12, 2024
An approach similar to the last problem, Index Pairs, could be used here. Simply iterating forward through the string and comparing the characters to the trie is enough to determine whether it exist in the dictionary or not. Then just keep a running total of the lengths of each word matched found in the trie, the length of the string minus this total gives you the left over letter count. This can be done without the use of an additioinal data structure, the DP array.
5
0
Comments
shekhart91 a year ago
class TrieNode:
def __init__(self):
self.children = [None] * 26 # Representing each character of the alphabet.
self.isEnd = False # To determine if the current TrieNode marks the end of a word.
class Trie:
def __init__(self):
se...
Devon Clarka year ago
Agree with @dlflann, DP unnecessarily complicates things and is actually LESS efficient than a forward traversal, similar to the previous question Index Pairs. I solved exactly the same way you did. The solution should be corrected!
Bekah Warnock2 months ago
This approach does not work if the words in the dictionary have overlap with one another. Although I did get a bit confused there because the problem statement said no overlap, but then I realized it was referring to not detecting overlapping words in the input text. Ov...