20 lines JAVA clean solution, easy to understand


  • 29
    D
    public class Solution {
    Map<Character,String> map =new HashMap();
    Set<String> set =new HashSet();
    public boolean wordPatternMatch(String pattern, String str) {
        if(pattern.isEmpty()) return str.isEmpty();
        if(map.containsKey(pattern.charAt(0))){
            String value= map.get(pattern.charAt(0));
            if(str.length()<value.length() || !str.substring(0,value.length()).equals(value)) return false;
            if(wordPatternMatch(pattern.substring(1),str.substring(value.length()))) return true;
        }else{
            for(int i=1;i<=str.length();i++){
                if(set.contains(str.substring(0,i))) continue;
                map.put(pattern.charAt(0),str.substring(0,i));
                set.add(str.substring(0,i));
                if(wordPatternMatch(pattern.substring(1),str.substring(i))) return true;
                set.remove(str.substring(0,i));
                map.remove(pattern.charAt(0));
            }
        }
        return false;
    }
    

    }


  • 12
    J

    Best solution on the board! One big thumb up. You don't need Set all at. Here is simplified version based on yours:

    public class Solution {
    Map<Character,String> map =new HashMap<Character, String>();
    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern.length() == 0)
        	return str.length() == 0;  
        if (map.containsKey(pattern.charAt(0))) {
        	String value = map.get(pattern.charAt(0));
        	if (value.length() > str.length() || !str.substring(0, value.length()).equals(value)) 
        		return false;
        	if (wordPatternMatch(pattern.substring(1), str.substring(value.length())))
        		return true;
        } else {
        	for (int i = 1; i <= str.length(); i ++) {
        		if (map.containsValue(str.substring(0, i))) continue;
        		map.put(pattern.charAt(0), str.substring(0, i));
        		if (wordPatternMatch(pattern.substring(1), str.substring(i))) {
        			return true;
        		} 
        		map.remove(pattern.charAt(0));
        	}
        }
        return false;
    } }

  • 0
    D

    The containsValue() method takes O(n) time, so your algorithm takes much more time.


  • 1
    J

    Not exactly cost O(n) more, since there are only 26 keys at most for this particular problem, it may cost slightly more time. It saves some space in SET on the other hand.


  • 0
    H

    haha, my solution is exactly same to your solution, like 99% similarity


  • 0
    F

    Nice Solution! I had exactly the same idea as yours, but the implementation is different. However, there is a detail confusing me a little. In the second 'if' statement, where the hash map has already included the key. Why can't we delete the key and the substring it's mapped to, if the length of the current string is smaller than the pattern or the pattern is a prefix of the string? If these two tests fail, then it means the current character-to-string mapping does not work. Why can't we delete it here? My first implementation deleted the mapping here, and it failed the last test case.


  • 0
    F

    By the way, I think in HashMap there is a method called containsValue(). You can use that method to check for duplicates, instead of creating another HashSet.


  • 0
    F

    I've figured it out why. Never mind.


  • 0
    6

    could you give some hint the reason why use continue there for the else part, when the map contains the key. thanks


  • 1
    W
    public boolean wordPatternMatch(String pattern, String str) {
      return match(pattern, str, new HashMap<>());
    }
    
    private boolean match(String pattern, String str, Map<Integer, String> map) {
      if (pattern.isEmpty()) return str.isEmpty();
      String s = map.get((int) pattern.charAt(0)), next = pattern.substring(1);
      if (s != null) return str.startsWith(s) ? match(next, str.substring(s.length()), map) : false;
      for (int i = 1, first = pattern.charAt(0); i <= str.length() - next.length(); i++) {
        if (map.containsValue(s = str.substring(0, i))) continue;
        map.put(first, s);
        if (match(next, str.substring(i), map)) return true;
        map.remove(first);
      }
      return false;
    }

  • 0
    F

    @673556617

    I assume you supposed to say when the map contains the "value". This is simply about disallowing two keys match to the same value in the map (given this is a bijection problem).


Log in to reply
 

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