Java backtracking solution


  • 0

    backtacking solution.
    Try on the characters in the pattern, using a hashmap to track the current status on the mapping.

    public class Solution {
        HashMap<Character, String> map = new HashMap<Character, String>();
        public boolean wordPatternMatch(String pattern, String str) {
            if(pattern == null || pattern.length() == 0) { 
                return str == null || str.length() == 0; 
            }
            char ch = pattern.charAt(0);
            if(map.containsKey(ch)){
                if(str.startsWith(map.get(ch))){
                    return wordPatternMatch(pattern.substring(1), str.substring(map.get(ch).length()));
                } else {
                    return false;
                }
            } else {
                int count = countAppearance(ch, pattern);
                for(int i = 1; i <= str.length() / count; i++) {
                    String val = str.substring(0,i);
                    if(!map.values().contains(val)) {
                        map.put(ch, val);
                        if(wordPatternMatch(pattern.substring(1), str.substring(i))) {
                            return true;
                        }
                        map.remove(ch);
                    }
                }
                return false;
            }
        }
        
        private int countAppearance(char ch, String str){
            int count = 0;
            for(int i = 0; i < str.length(); i++){
                if(ch == str.charAt(i)){
                    count++;
                }
            }
            return count;
        }
    }
    
    

Log in to reply
 

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