Trie-Trie-Trie!!! - Part 5

 An interesting problem that can be solved with Tries (there are other solutions too). You can create a simple trie and add all the digits to it. Then the idea is to have a Search function that given the original string and the current index, searches for any match in the trie starting at that index, and if there is a match, returns the jump offset. Complexity becomes the length of the string times the depth of the trie, which is a constant, hence the final time complexity is linear. Code is down below, cheers, ACC.

Convert Number Words to Digits - LeetCode

You are given a string s consisting of lowercase English letters. s may contain valid concatenated English words representing the digits 0 to 9, without spaces.

Your task is to extract each valid number word in order and convert it to its corresponding digit, producing a string of digits.

Parse s from left to right. At each position:

• If a valid number word starts at the current position, append its corresponding digit to the result and advance by the length of that word.
• Otherwise, skip exactly one character and continue parsing.

Return the resulting digit string. If no number words are found, return an empty string.

 

Example 1:

Input: s = "onefourthree"

Output: "143"

Explanation:

• Parsing from left to right, extract the valid number words "one", "four", "three".
• These map to digits 1, 4, 3. Thus, the final result is "143".

Example 2:

Input: s = "ninexsix"

Output: "96"

Explanation:

• The substring "nine" is a valid number word and maps to 9.
• The character "x" does not match any valid number word prefix and is skipped.
• Then, the substring "six" is a valid number word and maps to 6, so the final result is "96".

Example 3:

Input: s = "zeero"

Output: ""

Explanation:

• No substring forms a valid number word during left-to-right parsing.
• All characters are skipped and incomplete fragments are ignored, so the result is an empty string.

Example 4:

Input: s = "tw"

Output: ""

Explanation:

• No substring forms a valid number word during left-to-right parsing.
• All characters are skipped and incomplete fragments are ignored, so the result is an empty string.

 

Constraints:

• 1 <= s.length <= 105
• s contains only lowercase English letters.

public class Trie
{
    public Hashtable children = null;
    public int val = 0;

    public Trie()
    {
        children = new Hashtable();
        val = -1;
    }

    public void Add(string number, int value)
    {
        if (number.Length == 0) return;
        if (number.Length == 1)
        {
            if (!children.ContainsKey(number[0])) children.Add(number[0], new Trie());
            this.val = value;
            return;
        }
        if (!children.ContainsKey(number[0]))
            children.Add(number[0], new Trie());

        Trie child = (Trie)children[number[0]];
        child.Add(number.Substring(1), value);
    }

    public int Search(string str,
                      int index,
                      ref string value)
    {
        if (index >= str.Length || !children.ContainsKey(str[index]))
        {
            value = "";
            return -1;
        }
        else if (val != -1)
        {
            value = val.ToString();
            return index + 1;
        }
        Trie child = (Trie)children[str[index]];
        return child.Search(str, index + 1, ref value);
    }
}

public class Solution {
    public string ConvertNumber(string s)
    {
        Trie trieRoot = new Trie();

        trieRoot.Add("zero", 0);
        trieRoot.Add("one", 1);
        trieRoot.Add("two", 2);
        trieRoot.Add("three", 3);
        trieRoot.Add("four", 4);
        trieRoot.Add("five", 5);
        trieRoot.Add("six", 6);
        trieRoot.Add("seven", 7);
        trieRoot.Add("eight", 8);
        trieRoot.Add("nine", 9);

        string retVal = "";
        int index = 0;
        while (index < s.Length)
        {
            string value = "";
            int newIndex = trieRoot.Search(s, index, ref value);
            index = (newIndex == -1) ? index + 1 : newIndex;
            retVal += value;
        }

        return retVal;
    }
}