_648. Replace Words.md

648. Replace Words

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 07, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Hash Table, String, Trie

Acceptance Rate : 68.04 %

---

Solutions

• m648 Daily.py
• m648 v2 TRIE.py
• m648 v2 TRIE.java

Python

m648 Daily.py

# Daily

# Consistently pre slow at 20% percentile :l
# Makes sense as a brute force method to do a trie tho lol

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        output = sentence.split(' ')
        dictionary.sort(key=lambda x: len(x)) 
        for i in range(len(output)) :
            for dictVal in dictionary :
                if len(dictVal) <= len(output[i]) and dictVal == output[i][:len(dictVal)] :
                    output[i] = dictVal
                    break

        return ' '.join(output)

m648 v2 TRIE.py

# V2 using Trie method that consistently hits 98% runtime but hovers around 60% memory

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        
        # Trie setup
        trie = {}
        for root in dictionary :
            current = trie
            for c in root :
                if c in current :
                    current = current[c]
                else :
                    current[c] = {}
                    current = current[c]
            current['!'] = True # signifify end of dict word


        # Output calculation making use of trie
        output = sentence.split(' ')
        for i in range(len(output)) :
            current = trie
            progress = []

            for c in output[i] :
                if current.get('!', False): # Found shortest prefix
                    output[i] = ''.join(progress)
                    break
                if c in current :
                    progress.append(c)
                    current = current[c]
                    continue
                break

        return ' '.join(output)

Java

m648 v2 TRIE.java

// This could be better optimized by just having an array of 26 elements instead of a hashmap
// HashMap creation results in major cost time-wise and complexity (space) wise
// Since it's mapped to 26 lowercase chars, it's simpler that way since the spots will just be null
// when undeclared /shrug

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        helper trie = new helper();
        for (String s : dictionary) {
            helper currentNode = trie;
            for (Character c : s.toCharArray()) {
                if (currentNode.end) { // unnecessary to continue since exists a prefix that's shorter 
                    break;
                }

                if (currentNode.vals.containsKey(c)) {
                    currentNode = currentNode.vals.get(c);
                } else {
                    currentNode = currentNode.addCase(c);
                }
            }
            currentNode.end = true;
        }

        StringBuilder output = new StringBuilder();
        for (String word : sentence.split(" ")) {
            helper currentNode = trie;
            for (Character c : word.toCharArray()) {
                output.append(c);
                if (currentNode == null) {
                    continue;
                }

                if (currentNode.end) {
                    output.deleteCharAt(output.length() - 1);
                    break;
                }
                
                currentNode = currentNode.vals.getOrDefault(c, null);
            }
            output.append(" ");
        }

        output.deleteCharAt(output.length() - 1);
        return output.toString();
    }

    class helper {
        private HashMap<Character, helper> vals;
        private boolean end = false;
        
        public helper() {
            this.vals = new HashMap<>();
        }

        public helper addCase(Character c) {
            if (end) {
                return null;
            }

            vals.put(c, new helper());
            return vals.get(c);
        }
    }
}