A java solution by finding a correct way of breaking the string


  • 0
    H
    public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
    	// Counts the frequency of each character in the pattern.
    	HashMap<Character, Integer> frequencyMap = new HashMap<Character, Integer>();
        for (int i = 0; i < pattern.length(); ++i) {
            char c = pattern.charAt(i);
            if (!frequencyMap.containsKey(c)) frequencyMap.put(c, 0);
            frequencyMap.put(c, frequencyMap.get(c) + 1);
        }
        
        // Finds ways to break the str into pieces such that pieces mapped the same patten character have the same length.
        List<List<Integer>> breakWays = new ArrayList<List<Integer>>();
        List<Character> chs = new ArrayList<Character>(frequencyMap.keySet());
        findBreakWays(str.length(), 0, chs, frequencyMap, new ArrayList<Integer>(), breakWays);
        
        // Checks whether a certain break way is valid. 
        for (List<Integer> breakWay : breakWays) {
            if (isValid(pattern, str, chs, breakWay)) return true;
        }
        return false;
    }
    
    private void findBreakWays(int n, int index, List<Character> chs, HashMap<Character, Integer> frequencyMap, List<Integer> cur, List<List<Integer>> breakWays) {
        if (n < chs.size() - index) return;
        if (index == chs.size()) {
            if (n == 0) {
                breakWays.add(new ArrayList<Integer>(cur));
            }
            return;
        }
        for (int i = 1; i <= n / frequencyMap.get(chs.get(index)); ++i) {
            cur.add(i);
            findBreakWays(n - i * frequencyMap.get(chs.get(index)), index + 1, chs, frequencyMap, cur, breakWays);
            cur.remove(cur.size() - 1);
        }
    }
    
    private boolean isValid(String pattern, String str, List<Character> chs, List<Integer> breakWay) {
        HashMap<Character, Integer> lenMap = new HashMap<Character, Integer>();
        for (int i = 0; i < chs.size(); ++i) {
            lenMap.put(chs.get(i), breakWay.get(i));
        }
        int start = 0;
        HashMap<Character, String> map = new HashMap<Character, String>();
        HashSet<String> set = new HashSet<String>();
        for (int i = 0; i < pattern.length(); ++i){
            char c = pattern.charAt(i);
            String word = str.substring(start, start + lenMap.get(c));
            if (!map.containsKey(c)) {
                if (set.contains(word)) return false;
                map.put(c, word);
                set.add(word);
            } else if (!map.get(c).equals(word)) {
                return false;
            }
            start += lenMap.get(c);
        }
        return true;
    }
    

    }


  • 0
    D

  • 0
    H

    Yes, using backtracking can make the code cleaner, but I think my method is more efficient.


Log in to reply
 

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