Java Solution, easy understand


  • 17
    A
    public class WordDictionary {
        
        Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
        // Adds a word into the data structure.
        public void addWord(String word) {
            int index = word.length();
            if(!map.containsKey(index)){
                List<String> list = new ArrayList<String>();
                list.add(word);
                map.put(index, list);
            }else{
                map.get(index).add(word);
            }
            
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        public boolean search(String word) {
            int index = word.length();
            if(!map.containsKey(index)){
                return false;
            }
            List<String> list = map.get(index);
            if(isWords(word)){
                return list.contains(word);
            }
            for(String s : list){
                if(isSame(s, word)){
                    return true;
                }
            }
            return false;
        }
        
        boolean isWords(String s){
            for(int i = 0; i < s.length(); i++){
                if(!Character.isLetter(s.charAt(i))){
                    return false;
                }
            }
            return true;
        }
        
        boolean isSame(String a, String search){
            if(a.length() != search.length()){
                return false;
            }
            for(int i = 0; i < a.length(); i++){
                if(search.charAt(i) != '.' && search.charAt(i) != a.charAt(i)){
                    return false;
                }
            }
            return true;
        }
    }

  • 0
    S

    Straightforward solution! But I think mapping every character instead string is a more memory-saving approach.


  • 0
    Y

    public class WordDictionary {

    Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
    public void addWord(String word) {
        if (word != null && word.length() > 0){
            if (map.containsKey(word.length()))
                map.get(word.length()).add(word);
            else{
                List<String> list = new ArrayList<String>();
                list.add(word);
                map.put(word.length(), list);
            }
        }
    }
    public boolean search(String word) {
        if (map.size() < 1)    return false;
        if (word == null || word.length() < 1)  return false;
        boolean found = false;
        if (map.containsKey(word.length())){
            List<String> list = map.get(word.length());
            for (int i = 0; i < list.size(); i++){
                String s = list.get(i);
                for (int j = 0; j < s.length(); j++){
                    if (word.charAt(j) == s.charAt(j) || word.charAt(j) == '.'){
                        found = true;
                    }else{
                        found = false;
                        break;
                    }
                }
                if (found)  return true;
            }
        }else
            return false;
        return found;
    }
    

    }


  • 0
    Q

    I think isWord() is unnecessary.


  • 5
    H

    Thanks! Yes. I agree with you. Remove isWords() save time. Beat 94.8% java submissions.

    Map<Integer, List<String>> map = new HashMap<>();
    public void addWord(String word) {
        int index = word.length();
    	if (!map.containsKey(index)) {
    	    List<String> list = new ArrayList<>();
    	    list.add(word);
    		map.put(index, list);
    	} else {
    		map.get(index).add(word);
    	}
    }
    
    
    public boolean search(String word) {
      int index = word.length();
      if (!map.containsKey(index)) {
          return false;
      }
      
      List<String> list = map.get(index);
      for(String s : list) { 
          if(isSame(s, word)) { // when word has '.'
              return true;
          }
      }
      return false;
    }
    
    public boolean isSame(String s, String word) { // word has '.'
        for (int i = 0; i < s.length(); i++) {
            if (word.charAt(i) != '.' && s.charAt(i) != word.charAt(i)) {
                return false;
            }
        }
        return true;
    }
    

Log in to reply
 

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