Java solution, 12 lines, HashSet


  • 4

    Why it is a hard problem? Anyway...

    public class Solution {
        public String replaceWords(List<String> dict, String sentence) {
            if (dict == null || dict.size() == 0) return sentence;
            
            Set<String> set = new HashSet<>();
            for (String s : dict) set.add(s);
            
            StringBuilder sb = new StringBuilder();
            String[] words = sentence.split("\\s+");
            
            for (String word : words) {
                String prefix = "";
                for (int i = 1; i <= word.length(); i++) {
                    prefix = word.substring(0, i);
                    if (set.contains(prefix)) break;
                }
                sb.append(" " + prefix);
            }
            
            return sb.deleteCharAt(0).toString();
        }
    }
    

  • 2
    J

    Because your solution is a naive one.
    I believe there will be more test cases which your solution cannot pass in the future.
    You can optimize your solution with Trie, which makes the problem harder.


  • 0
    M

    C++ version

    class Solution {
    public:
        string replaceWords(vector<string>& dict, string sentence) {
            unordered_set<string> dict1;
            for(const string& s:dict) 
                dict1.insert(s);
            string sub, result;
            for(int i=0; i<sentence.length();) {
                sub += sentence[i];
                if(sentence[i]==' ') {
                    result += sub;
                    sub = "";
                }
                else {
                    if(dict1.find(sub)!=dict1.end()) {
                        result += sub;
                        sub = "";
                        while(i<sentence.length() && sentence[i]!=' ') i++;
                        continue;
                    }
                }
                i++;
            }
            result += sub;
            return result;
        }
    };
    

  • 0
    I

    This is a straightforward method but I think the time complexity would be a flaw when the sentence contains too many words and each word contains too may letters.


  • 0
    M

    Given the conditions that the word length or the sentence length is in magnitude of thousands, this is an excellent solution.


  • 1

    Similar idea, but no HashSet or StringBuilder used. Here is my code:

    public String replaceWords(List<String> dict, String sentence) {
            dict.sort((a, b) -> a.length() - b.length());
            String[] words = sentence.split("\\s+");
            for (int i = 0; i < words.length; i++) {
                String word = words[i];
                for (String root: dict) {
                    if (word.startsWith(root)) {
                        words[i] = root;
                        break;
                    }
                }
            }
            return String.join(" ", words);
        }
    

  • 0

    @dilyar I make the exact solution!

    public String replaceWords(List<String> dict, String sentence) {
        Collections.sort(dict, Comparator.comparingInt(String::length));
        String[] words = sentence.split(" ");
        for(int i = 0; i < words.length; i++) {
            String word = words[i];
            for(String e : dict) {
                if(word.startsWith(e)) {
                    words[i] = e;
                    break;
                }
            }
        }
        return String.join(" ", words);
    }

Log in to reply
 

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