Java solution, 12 lines, HashSet


  • 5

    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();
        }
    }
    

  • 3
    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);
    }

  • 0
    Z

    @jtimberlakers no test cases can not pass


  • 0
    Z

    @zhaiFuture this is the same time complexity with Trie


  • 0
    Z

    @zhaiFuture said in Java solution, 12 lines, HashSet:

    @zhaiFuture this is the same time complexity with Trie

    Although this is 10 times slower than Trie


Log in to reply
 

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