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.


Log in to reply
 

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