Time Limit Exceeded on Word Break II


  • 0
    D

    I got down a recursive backtracking solution,which according to me is the only way we can do this one. But I got a TLE on this. Any idea where I am going wrong here?

    public class Solution {
        private void getWordBreaks(char[] s, int start, Set<String> wordDict, int end, List<String> ret, List<String> cur) {
            if (start > end) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < cur.size(); i++) {
                    sb.append(cur.get(i));
                    if (i < cur.size() - 1)
                        sb.append(' ');
                }
                ret.add(sb.toString());
                return;
            }
            for (int i = start; i <= end; i++) {
                String subs = String.valueOf(Arrays.copyOfRange(s, start, i + 1));
                if (wordDict.contains(subs)) {
                    cur.add(subs);
                    getWordBreaks(s, i + 1, wordDict, end, ret, cur);
                    cur.remove(cur.size() - 1);
                }
            }
        }
    
        public List<String> wordBreak(String s, Set<String> wordDict) {
            List<String> ret = new ArrayList<String>();
            if (s == null || s.isEmpty()) return ret;
            List<String> cur = new ArrayList<String>();
            char[] arr = s.toCharArray();
            getWordBreaks(arr, 0, wordDict, s.length() - 1, ret, cur);
            return ret;
        }
    }

Log in to reply
 

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