Java DFS Solution 8ms


  • 0
    M

    Actually similar idea as Subsets

    public class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> res = new ArrayList<>();
            List<String> list = new ArrayList<>();
            DFS(res, list, 0, s, 0);
            return res;
        }
        private void DFS(List<List<String>> res, List<String> list, int start, String s, int len) {
            if (len == s.length()) {
               res.add(new ArrayList<String>(list)); 
            }
            for (int i = 1; i <= s.length(); i++) {
                if (start + i > s.length()) break;
                String tmp = s.substring(start, start + i);
                if (!palindrome(tmp)) {
                    continue;
                }
                list.add(tmp);
                DFS(res, list, start + i, s, len + tmp.length());
                list.remove(list.size() - 1);
            }
        }
        private boolean palindrome(String s) {
            int len = s.length();
            int lo = 0, hi = len - 1;
            while (lo < hi) {
                if (s.charAt(lo) != s.charAt(hi)) {
                    return false;
                }
                lo++;
                hi--;
            }
            return true;
        }
    }

Log in to reply
 

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