my dp solution with no hashmap


  • 0
    public List<String> wordBreak(String s, List<String> wordDict) {
            int n = s.length();
            ArrayList<String>[] memo = new ArrayList[n];
            for(int i = 0;i < n;i++) memo[i] = new ArrayList<>();
            boolean[] visited = new boolean[n];
            for(String word:wordDict) {
                int len = word.length();
                for(int i = 0;i + len <= n;i++) {
                    if(s.substring(i,i+len).equals(word)) memo[i].add(word);
                }
            }
            return check(memo,0,visited);
        }
    public List<String> check(List<String>[] memo,int i,boolean[] visited) {
            if(visited[i]) return memo[i];
            List<String> currList = memo[i];
            List<String> newList = new ArrayList<>();
            for(String currString:currList) {
                int currLen = currString.length();
                if(i + currLen == memo.length) {
                    newList.add(currString);
                    continue;
                }
                List<String> nextList = check(memo,i+currLen,visited);
                if(nextList == null || nextList.size() == 0) continue;
                for(String nextString:nextList) {
                    String toAdd = currString + " " + nextString;
                    newList.add(toAdd);
                }
            }
            memo[i] = newList;
            visited[i] = true;
            return newList;
        }

Log in to reply
 

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