Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Extra Characters in a String (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

# class TrieNode:
#     def __init__(self):
#         self.children = {}  # Represents 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):
        self.root = TrieNode()

    def insertword(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.isEnd = True

class Solution:
    def minExtraChar(self, s, dictionary):
        # Make the tree
        trie = Trie()

        # Build the tree
        for word in dictionary:
            trie.insertword(word)

        # pointers for current word and extra chars
        curword,extras,c = 0,0,0
A

Anonymous

· 2 years ago

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_the_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.end_of_the_word = True

class Solution:
    def minExtraChar(self, s, words):
        # gen Trie with <words>
        t = Trie()
        for word in words:
            t.insert(word)

        # while left pointer less than the end of the <s>,
        # check all substrings
        l = 0
        found_words_len = 0
        l_need_to_jump = False
        while l < len(s):
            node = t.
A

Anonymous

· 2 years ago

Looks like submissions are broken on this one,

any submission returns this error "Unknown Error - Check your Input".

Submissions in other tasks works fine

A

Anonymous

· 3 years ago

I am looking into problems to learn Dynamic Programming. I think this was not a good example of a problem that needs such a thing. In my view, the proposed solution is over engineered as you literally need only a counter. If you want to improve this solution you can pass as a parameter to the trie the string and the two pointers (left, right) so you don't create a new string each time.

import java.util.Map;
import java.util.HashMap;
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();  // Representing each character of the alphabet.
    boolean isEnd = false;  // To determine if the current TrieNode marks the end of a word.
}

class Trie { 
    TrieNode root; 

    Trie() {
        root = new TrieNode();
    }

    void insert(String word) {
        var
Show 1 reply
A

Anonymous

· 3 years ago

additionally, key error message I was getting was giving completely incorrect line number.

Reading Progress

0%

Vote for new content