Simple and clean Java backtracking solution


  • 0
    J
    public class Solution {
    	Map<Character, String> f = new HashMap<>();
    	Map<String, Character> f_inverse = new HashMap<>();
    
    	boolean solve(char[] p, int i, String s) {
    		if (i >= p.length && s.length() == 0) return true;
    		else if (i < p.length && s.length() == 0) return false;
    		else if(i >= p.length && s.length() > 0) return false;
    
    		for (; i < p.length; i++) {
    			if (f.containsKey(p[i])) {
    				String y = f.get(p[i]);
    				if (s.length() < y.length())
    					return false;
    				if (s.substring(0, y.length()).equals(y)) {
    					String nxt = s.substring(y.length());
    					return solve(p, i + 1, nxt);
    				}
    				return false;
    			} else {
    				for (int j = 1; j <= s.length(); j++) {
    					String nxt = s.substring(0, j);
    					if (f_inverse.containsKey(nxt))
    						continue;
    
    					f.put(p[i], nxt);
    					f_inverse.put(nxt, p[i]);
    					
    					if (solve(p, i + 1, s.substring(j))) return true;
    
    					f.remove(p[i]);
    					f_inverse.remove(nxt);
    				}
    				return false;
    			}
    		}
    
    		return false;
    	}
    
    	public boolean wordPatternMatch(String pattern, String str) {
    		return solve(pattern.toCharArray(), 0, str);
    	}
    }

Log in to reply
 

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