Java 6ms solution, beating 99%


  • 1
    Y

    DFS with two hash maps to ensure O(1) lookup time

    public class Solution {
        // DFS
        public boolean wordPatternMatch(String pattern, String str) {
    		return helper(pattern, str, 0, new HashMap<Character, String>(),
    				new HashMap<String, Character>());
    	}
    
    	private boolean helper(String pattern, String str, int patternPos,
    			Map<Character, String> char2string,
    			Map<String, Character> string2char) {
    		if (patternPos == pattern.length()) {
    			if (str.length() == 0) {
    				return true;
    			}
    			return false;
    		}
    		// there are only two cases of valid mapping
    		// case 1. char and substring exist as key in two maps, and map to each
    		// other
    		// case 2. char and substring do not exist in the two maps, then we
    		// insert the mapping
    		char currPat = pattern.charAt(patternPos);
    		if (!char2string.containsKey(currPat)) {
    			for (int l = 1; l <= str.length() - (pattern.length() - patternPos)
    					+ 1; l++) {
    				String substr = str.substring(0, l);
    				if (!string2char.containsKey(substr)) { // check if case 2 is satisfied
    					char2string.put(currPat, substr);
    					string2char.put(substr, currPat);
    					if (helper(pattern, str.substring(l), patternPos + 1,
    							char2string, string2char)) {
    						return true;
    					}
    					char2string.remove(currPat, substr);
    					string2char.remove(substr, currPat);
    				}
    			}
    		} else {
    			// check if case 1 is satisfied
                if (str.startsWith(char2string.get(currPat)) && 
                    string2char.containsKey(char2string.get(currPat)) &&
                    string2char.get(char2string.get(currPat)) == currPat && 
                    helper(pattern, str.substring(char2string.get(currPat).length()), patternPos + 1, char2string, string2char)) {
                        return true;
                    }
    		}
    		return false;
    	}
    }

  • 1

    It's very similar to the solution I just came up with, with the following differences:

    1. I used an array to map characters to strings. There must be a reason the problem states that only lowercase letters are used! But then again it doesn't say "basic Latin", so my solution is not strictly correct in that sense.

    2. I used another index parameter similar to patternPos to avoid unnecessary copying caused by substring.

    3. I used a set for string2char because the value is not really needed.

    4. I moved backtracking in char2string out of the loop because it's going to be replaced with another string on the next iteration anyway, so why bother removing it?

    In the end, it runs in 3 ms. Funny enough, when I was coding it, I expected it to be very slow since it's a pretty much naive algorithm and the problem is tagged "hard". Here is the code:

    private static final int LETTER_A = 'a';
    private static final int LETTERS_COUNT = 26;
    
    public boolean wordPatternMatch(String pattern, String str) {
        String[] fixed = new String[LETTERS_COUNT];
        Set<String> used = new HashSet<>();
        return matches(pattern, 0, str, 0, fixed, used);
    }
    
    private static boolean matches(String pattern, int p, String str, int s, String[] fixed, Set<String> used) {
        if (p == pattern.length()) {
            return s == str.length();
        }
        if (s == str.length()) {
            return false;
        }
        char pc = pattern.charAt(p);
        String r = fixed[pc - LETTER_A];
        if (r != null) {
            if (s + r.length() <= str.length() && str.regionMatches(s, r, 0, r.length())) {
                return matches(pattern, p + 1, str, s + r.length(), fixed, used);
            } else {
                return false;
            }
        }
        for (int i = s + 1; i <= str.length() - (pattern.length() - (p + 1)); ++i) {
            String substr = str.substring(s, i);
            if (used.contains(substr)) {
                continue;
            }
            fixed[pc - LETTER_A] = substr;
            used.add(substr);
            if (matches(pattern, p + 1, str, i, fixed, used)) {
                return true;
            }
            used.remove(substr); // backtrack
        }
        fixed[pc - LETTER_A] = null; // backtrack
        return false;
    }
    

Log in to reply
 

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