Java HashMap Solution, Some Explanation


  • 0

    I used a hashset and a hashmap for this problem. The hashset is used to store the dictionary. Use the hashset to check if the substring occurs in the dictionary. Hashmap is used to memorize the checked word and their corresponding root so if you meet them next time, you do not need to go through the string checking substrings one by one again.

    public String replaceWords(List<String> dict, String sentence) {
        StringBuilder res = new StringBuilder(); 
        String[] sentences = sentence.split(" ");
        Set<String> roots = new HashSet<>();
        Map<String, String> memo = new HashMap<>();
        for (String r: dict) {
            roots.add(r);
        }
        for(int i = 0; i < sentences.length; i++) {
            if (memo.containsKey(sentences[i])) {
                res.append(memo.get(sentences[i]));
            }
            else {
                boolean found = false;
                for (int j = 0; j <= sentences[i].length(); j++) {
                    if (roots.contains(sentences[i].substring(0,j))) {
                        memo.put(sentences[i], sentences[i].substring(0,j));
                        res.append(sentences[i].substring(0,j));
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    res.append(sentences[i]);
                }
            }
            if (i < sentences.length - 1) {
                res.append(' ');
            }
        }
        return res.toString();
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.