A simple Java solution using Map<String, String>


  • 3
    S
    public class ValidWordAbbr {
    
    Map<String, String> map = new HashMap<>();
    
    public ValidWordAbbr(String[] dictionary) {
        for (String dic : dictionary) {
            String key = getKey(dic);
            if (map.containsKey(key)) {
                map.put(key, "");
            } else {
                map.put(key, dic);
            }
        }
    }
    
    public boolean isUnique(String word) {
        String key = getKey(word);
        return !map.containsKey(key) || map.get(key).equals(word);
    }
    
    private String getKey(String word) {
        String key = word.charAt(0) + Integer.toString(word.length() - 2) + word.charAt(word.length() - 1);
        return key;
    }
    

    }


  • 0
    H

    Sam solution except I use null as the hash value for duplicates


  • 0
    M

    (1) getKey() is not right. Your getKey("it") returns "i0t" instead of "it" (2) Also, I think we should consider word==null case.


  • 0
    S

    Good catch!!


  • 0
    B

    Your solution fails in the following case:

    Say the dictionary contains ["happy", "happy"] and your word is: "happy"

    After the constructor has been invoked, your map will contain:
    {"h3y": ""}

    Now when isUnique is called on our word "happy", we will generate the key, "h3y", and then see that our map contains the key, but the value "" !.equals("happy") and we will return false.

    However the problem states that we should return true if there is no other word in the dictionary with the same abbreviation.


  • 0
    Y

    As the comments mentioned, the original code doesn't pass case ["happy", "happy"] and isUnique("happy") should be true. But the original code return false.

    Below is an updated version. It uses HashMap to keep track of the added word...so it uses more space. Is there any better solution that use less space?

    public class ValidWordAbbr {
    	Map<String, Integer> map = new HashMap<String,Integer>();
    	HashSet<String> myset = new HashSet<String>();
    	public ValidWordAbbr(String[] dictionary) {
    		for(String word: dictionary) {
    			
    			String key = getKey(word);
    			if(map.containsKey(key)){
    				if(myset.add(word))
    					map.put(key, map.get(key)+1);
    					
    			} else {
    				map.put(key, 1);
    				myset.add(word);
    			}
    		}
    	}
    	
    	public boolean isUnique(String word) {
    		if(word.length() == 0) {
    			return true;
    		}
    		String key = getKey(word);
    		
    		return !map.containsKey(key) || 
    				(map.get(key)==1 && !myset.add(word));
    	}
    	
    	private String getKey(String word) {
    		String key;
    		if(word.length() == 0||word.length()==1||word.length()==2){
    			key = word;
    		} else {
    			key = word.charAt(0)+Integer.toString(word.length()-2) + word.charAt(word.length()-1);
    		}
    		return key;
    	}
    }

  • 0
    Z
    This post is deleted!

  • 0
    Z
    HashMap<String,String> map=new HashMap<String,String>();
    public ValidWordAbbr(String[] dictionary) {
        for(String s:dictionary)
        {
            if(s.length()<=2)continue;
            String c= s.substring(0,1)+String.valueOf(s.length()-2)+s.substring(s.length()-1);
            if(!map.containsKey(c))
            {
                map.put(c,s);
            }else
            {
                if(!map.get(c).equals(s))//check  duplicate string
                map.put(c,"");
            }
        }
        
    }
    
    public boolean isUnique(String word) {
        if(word.length()<=2)return true;
       
        String s=word.substring(0,1)+String.valueOf(word.length()-2)+word.substring(word.length()-1);
        return !map.containsKey(s)||map.get(s).equals(word);
        
        
    }

Log in to reply
 

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