Always have a problem that need lots of memory to remember the path


  • 0
    D

    I always find it difficult to solve this kind of problem: whether some pattern is followed and return all the valid result. My solution is combining the "true or false" algorithm with an array that can remember the path I take, and usually, this path will end with false, but I have to save them in the memory before I know this path is actually invalid. On the other hand, when I am in old state j and find myself match the pattern, I want to add i to j, but I cannot add it directly because other i might also start from this j.

    For example:
    Suppose we already know the path:
    0->3->6->8
    And we find both i = 10 and i = 12 can be the next path, so I have to copy the entire path from the last state to current:
    0->3->6->8 COPY to:
    0->3->6->8
    0->3->6->8
    And add 10 and 12 at the end:
    0->3->6->8->10
    0->3->6->8->12

    my method is so stupid that needs copy all the sub matched path every time, I looked at some TOP solutions but find that most of them use recursive method(And I think this way we will not have to copy all the finally invalid path? Because we are starting from bottom, and keep calling function until we reach the end), but I just want to know is there any way to resolve this "copy and add new path element" problem?
    (Or for the path problem bottom-up method is preferred?)

    This is my stupid code for handling path copy, but I am confused about its performance because it only takes 10ms beats 97%, I think this is not a very good solution for copy problem:

    public class Solution {
        public List<String> wordBreak(String s, List<String> wordDict) {
            if (s.length() == 0 || wordDict.size() == 0) return new ArrayList<String>();
            Set<String> dic = new HashSet<String>();
            int max = wordDict.get(0).length();
            int min = max;
            for (String word: wordDict) {
                dic.add(word);
                if (word.length() < min) {
                    min = word.length();
                } else if (word.length() > max) {
                    max = word.length();
                }
            }
            boolean[] canBreak = new boolean[s.length() + 1];
            if (!isWordBreak(s, dic, min, max)) return new ArrayList<String>();
            
            List<List<List<Integer>>> resArray =
                new ArrayList<List<List<Integer>>>(s.length() + 1);
            for (int i = 0; i < s.length() + 1; i++) {
                resArray.add(null);
            }
            
            canBreak[0] = true;
            resArray.set(0, new ArrayList<List<Integer>>());
            resArray.get(0).add(new ArrayList<Integer>());
            resArray.get(0).get(0).add(0);
            for (String word: wordDict) {
                dic.add(word);
                int n = word.length();
                if (min > word.length()) {
                    min = n;
                } else if (max < word.length()) {
                    max = n;
                }
            }
    
            for (int i = 1; i < s.length() + 1; i++) {
                int n = Math.max(i - max, 0);
                for (int j = Math.max(i - min, 0); j >= n; j--) {
                    if (canBreak[j] && dic.contains(s.substring(j, i))) {
                        canBreak[i] = true;
                        List<List<Integer>> prevIdxListArray = resArray.get(j);
                        List<List<Integer>> currIdxListArray = resArray.get(i);
                        if (currIdxListArray == null) {
                            currIdxListArray = new ArrayList<List<Integer>>();
                            for (List<Integer> prevIdxList: prevIdxListArray) {
                                List<Integer> listI = new ArrayList<Integer>();
                                for (int idx: prevIdxList) {
                                    listI.add(idx);
                                }
                                listI.add(i);
                                currIdxListArray.add(listI);
                            }
                            resArray.set(i, currIdxListArray);
                        } else {
                            for (List<Integer> prevIdxList: prevIdxListArray) {
                                List<Integer> listI = new ArrayList<Integer>();
                                for (int idx: prevIdxList) {
                                    listI.add(idx);
                                }
                                listI.add(i);
                                currIdxListArray.add(listI);
                            }
                        }
                    }
                }
            }
            
            List<String> res;
            if (canBreak[s.length()]) {
                List<List<Integer>> idxListArray = resArray.get(s.length());
                res = new ArrayList<String>(idxListArray.size());
                for (List<Integer> idxList: idxListArray) {
                    StringBuilder sb = new StringBuilder();
                    int start = 0;
                    for (int i = 1; i < idxList.size(); i++) {
                        int end = idxList.get(i);
                        sb.append(s.substring(start, end) + " ");
                        start = end;
                    }
                    sb.setLength(sb.length() - 1);
                    res.add(sb.toString());
                }
            } else {
                res = new ArrayList<String>();
            }
            
            return res;
        }
        
        private boolean isWordBreak(String s, Set<String> dic, int min, int max) {
            boolean[] canWordBreak = new boolean[s.length() + 1];
            canWordBreak[0] = true;
            for (int i = 1; i < s.length() + 1; i++) {
                // Since we know the max length and min length of dic's word,
                // we can limit the search range
                int n = Math.max(i - max, 0);
                for (int j = Math.max(i - min, 0); j >= n; j--) {
                    // Every time check stiring 0...j and j...i is breakable,
                    // if so 0......i is breakable
                    if (canWordBreak[j] && dic.contains(s.substring(j, i))) {
                        canWordBreak[i] = true;
                        break;
                    }
                }
            }
            // The last one in the array is answer
            return canWordBreak[s.length()];
        }
    }
    

    Thanks a lot!


Log in to reply
 

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