2014年5月12日星期一

Loop Solution - Substring with Concatenation of All Words

The idea below is very simple, create a count Map for L, and inside S, cut same length as L.size() * L[0].length(). Loop this subString inside S, and compare with the Map for L. If match, add current index, otherwise move to next. index + L * L[0] < S.length()

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        if(S == null || L == null ||L.length == 0 || S.length() < (L[0].length() * L.length)){
            return new ArrayList<Integer>();
        }
        //ArrayList<Integer> results = new ArrayList<Integer>();
        return findSubstringOps(S, L);
    }
   
    private ArrayList<Integer> findSubstringOps(String S, String[] L){
        ArrayList<Integer> results = new ArrayList<Integer>();
        if(S == null || L == null ||L.length == 0 || S.length() < (L[0].length() * L.length)){
            return results;
        }
        int index = 0;
        int wordSize = L[0].length();
        while(index <= S.length() - (wordSize * L.length)){
            int secondIndex = index;
            boolean found = true;
            HashMap<String, Integer> process = buildMap(L);
            while(secondIndex < index + wordSize * L.length){
                String cur = S.substring(secondIndex, secondIndex + wordSize);
                if(process.containsKey(cur)){
                    if(process.get(cur) == 0){
                        found = false;
                        break;
                    }
                    process.put(cur, process.get(cur) - 1);
                    secondIndex += wordSize;
                }else{
                    found = false;
                    break;
                }
            }
            if(found){
                Set<String> keys = process.keySet();
                Iterator it = keys.iterator();
                while(it.hasNext()){
                    if(process.get((String) it.next())  != 0){
                        found = false;
                        break;
                    }
                }
            }
            if(found) results.add(index);
            index++;
        }
        return results;
    }
   
    private HashMap<String, Integer> buildMap(String[] L){
        HashMap<String, Integer> process = new HashMap<String, Integer>();
        for(String lp : L){
            if(process.containsKey(lp)){
                process.put(lp, process.get(lp) + 1);
            }else{
                process.put(lp, 1);
            }
        }
        return process;
    }
}

没有评论: