Share my solution using frequent sequence mining


  • 0
    A

    The idea is simply avoiding redundantly computing the letter combinations for same substrings. For example, "12123", the code only calculates once for the substring "12" and then combine the mappings for "12", "12" and "3" together.

    The benefit would be reducing the recursion depth. But it would still have the same number of leaf nodes.
    The magnitude of the time complexity would not change in the worst the scenario. But in practice, it would have a better performance if there are frequent subsequences in the "digits"

    The code is a little bit long. Please suggest some improvements over the code.

     public class Solution {
      public List<String> letterCombinations(String digits) {
            if(digits.length() ==0 ){
                return new ArrayList<String>();
            }
    		int[] seqspan = new int[digits.length()];
    		HashMap<String, ArrayList<Integer>> string2indexs = new HashMap<String, ArrayList<Integer>>();
    		identifySubsequence(seqspan, string2indexs, digits);
    		HashMap<String, ArrayList<String>> partialmappings = new HashMap<String, ArrayList<String>>();
    		identifyCombinationforSubseq(partialmappings, string2indexs);
    		List<String> ret = combinSubseqs(partialmappings, digits, seqspan);
    		return ret;
    	}
    	public List<String> combinSubseqs(HashMap<String, ArrayList<String>> partialmappings, String digits, int[] seqspan){
    		List<String> ret = new ArrayList<String>();
    		ret.add("");
    		int ptr = 0;
    		String curvalue = "";
    		while (ptr < digits.length()) {
    			if (seqspan[ptr] == 1) {
    				curvalue += digits.charAt(ptr);
    				ptr ++;
    			} else {
    				ArrayList<String> partials = new ArrayList<String>();
    				generatePartialMappings(curvalue, 0, "", partials);
    				ret = appendStrings(ret, partials);
    				curvalue = digits.substring(ptr, ptr + seqspan[ptr]);
    				ptr = ptr + seqspan[ptr];
    			}
    		}
    		if (curvalue.length() > 0) {
    			ArrayList<String> partials = new ArrayList<String>();
    			generatePartialMappings(curvalue, 0, "", partials);
    			ret = appendStrings(ret, partials);
    		}
    		return ret;
    	}
    	public void identifyCombinationforSubseq(
    			HashMap<String, ArrayList<String>> partialmappings, HashMap<String, ArrayList<Integer>> string2indexs) {
    		for (String key : string2indexs.keySet()) {
    			if (string2indexs.get(key).size() > 1) {
    				ArrayList<String> tmp = new ArrayList<String>();
    				generatePartialMappings(key, 0, "", tmp);
    				partialmappings.put(key, tmp);
    			}
    		}
    	}
    
    	public List<String> appendStrings(List<String> pre, List<String> suf) {
    		List<String> ret = new ArrayList<String>();
    		for (String p : pre) {
    			for (String s : suf) {
    				ret.add(p + s);
    			}
    		}
    		return ret;
    	}
    
    	public final String[][] mapping = { { " " }, {}, { "a", "b", "c" },
    			{ "e", "d", "f" }, { "g", "h", "i" }, { "j", "k", "l" },
    			{ "m", "n", "o" }, { "p", "q", "r", "s" }, { "t", "u", "v" },
    			{ "w", "x", "y", "z" } };
    
    	public void generatePartialMappings(String map, int index, String path,
    			ArrayList<String> result) {
    		if (index >= map.length()) {
    			result.add(path);
    			return;
    		}
    		char c = map.charAt(index);
    		String[] letters = mapping[(int) c - 48];
    		if (letters.length == 0) {
    			generatePartialMappings(map, index + 1, path, result);
    		} else {
    			for (String s : letters) {
    				generatePartialMappings(map, index + 1, path + s, result);
    			}
    		}
    	}
    
    	public void identifySubsequence(int[] seqspan,
    			HashMap<String, ArrayList<Integer>> map, String digits) {
    		ArrayList<Integer> toCheck = new ArrayList<Integer>();
    		int span = 1;
    		for (int i = 0; i < seqspan.length; i++) {
    			toCheck.add(i);
    			seqspan[i] = 1;
    		}
    		while (toCheck.size() > 0) {
    			span++;
    			ArrayList<Integer> candidates = new ArrayList<Integer>();
    			for (int i = 0; i < toCheck.size(); i++) {
    				if (i + span <= seqspan.length) {
    					String sub = digits.substring(i, i + span);
    					if (map.containsKey(sub)) {
    						map.get(sub).add(i);
    						candidates.add(i);
    						for(int val: map.get(sub)){
    							seqspan[val] = span;
    						}
    					} else {
    						ArrayList<Integer> indexes = new ArrayList<Integer>();
    						indexes.add(i);
    						map.put(sub, indexes);
    					}
    				}
    			}
    			toCheck.clear();
    			toCheck = candidates;
    		}
    	}
    }

Log in to reply
 

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