Share my Java solution, Use dfs to solve an equation of token length and then match


  • 0
    Y

    My idea is to analyze the pattern first. I used an array of length 26 to store the appearance times of a particular character. For the pattern "abab", the array called times would be like

    [2, 2, 0, 0, 0, 0, ..... Many zeros]

    Then I tried to solve an equation on the str length.

    2 * x + 2 * y = 14;

    I used dfs to solve this problem. After I have all the permutations, for example in case "abab", "redblueredblue" permute array would be [2, 12, 0, 0, 0, 0, .... Many zeros]. So I know that for char a, the length is 2 / 2 = 1. The length for b is 12 / 2 = 6. Then I match these two string using a similar approach in Word Pattern 1.

    A better way could do so is to whenever a result permutation comes out, check 2 strings at once. Thus avoid lots of dfs calls.

    For the time complexity, I am not quite sure, if you know, please analyze for me. I guess it is O(n^2) as the pattern length need to gradually grow to the string length.

    public boolean wordPatternMatch(String pattern, String str) {
    	int pLen = pattern.length();
    	int sLen = str.length();
    
    	if (pLen == 0 && sLen == 0) {
    		return true;
    	}
    
    	if (pLen <= 0) {
    		return false;
    	}
    
    	if (sLen <= 0) {
    		return false;
    	}
    
    	List<int[]> results = new ArrayList<>(256);
    	int[] permute = new int[26];
    	Arrays.fill(permute, 0);
    	for (int i = 0; i < pLen; i++) {
    		int index = pattern.charAt(i) - 'a';
    		permute[index]++;
    	}
    	int[] times = new int[26];
    	System.arraycopy(permute, 0, times, 0, 26);
    	dfs(results, permute, sLen - pLen, 0, times);
    
    	int size = results.size();
    	HashMap<Character, String> pToS = new HashMap<>(pLen * 2);
    	HashMap<String, Character> sToP = new HashMap<>(pLen * 2);
    	for (int j = 0; j < size; j++) {
    		int[] pmt = results.get(j);
    
    		pToS.clear();
    		sToP.clear();
    		boolean success = true;
    		int start = 0;
    		int end = 0;
    		for (int i = 0; i < pLen; i++) {
    			char p = pattern.charAt(i);
    			int index = p - 'a';
    			end = start + pmt[index] / times[index];
    			String s = str.substring(start, end).intern();
    			start = end;
    			boolean ps = pToS.containsKey(p);
    			boolean sp = sToP.containsKey(s);
    
    			if (ps && sp) {
    				if (p == sToP.get(s) && s == pToS.get(p)) {
    					continue;
    				} else {
    					success = false;
    					break;
    				}
    			} else if (ps) {
    				success = false;
    				break;
    			} else if (sp) {
    				success = false;
    				break;
    			} else {
    				pToS.put(p, s);
    				sToP.put(s, p);
    			}
    		}
    
    		if (success) {
    			return true;
    		}
    	}
    
    	return false;
    }
    
    public void dfs(List<int[]> results, int[] permute, int lenLeft, int pos, int[] times) {
    	if (pos >= 26) {
    		if (lenLeft == 0) {
    			results.add(permute);
    		}
    		return;
    	}
    
    	if (lenLeft == 0) {
    		results.add(permute);
    		return;
    	}
    
    	if (permute[pos] <= 0) {
    		dfs(results, permute, lenLeft, pos + 1, times);
    		return;
    	}
    
    	int loopTimes = lenLeft / times[pos] + 1;
    	for (int i = 0; i < loopTimes; i++) {
    		int[] newPermute = new int[26];
    		System.arraycopy(permute, 0, newPermute, 0, 26);
    		newPermute[pos] = newPermute[pos] + times[pos] * i;
    		dfs(results, newPermute, lenLeft - times[pos] * i, pos + 1, times);
    	}
    }

  • 0
    D

Log in to reply
 

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