Any way to reduce the runtime?


  • 1
    L

    It costs roughly 528ms to run the code. It is accepted but Im sure there is some improvement I can do.

    public class Solution {
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        helper(s, 0, res, new ArrayList<String>());
        return res;
    }
    
    private void helper(String s,int start, ArrayList<ArrayList<String>> res, ArrayList<String> item) {
        if(start == s.length()) {
            res.add(new ArrayList<String>(item));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String cut = s.substring(start, i +1 );
            if(check(cut)) {
                item.add(cut);
                helper(s, i + 1, res,item);
                item.remove(item.size() - 1);
            }
        }
    }
    
    private boolean check(String s) {
        StringBuilder sb = new StringBuilder(s);
        return s.equals(sb.reverse().toString());
    }
    

    }

    Any answer is appreciated!!


  • 0
    S

    I would say, using Java 500+ ms is a reasonable time cost. However, would you mind elaborate time complexity?


  • 2
    E

    Here is my code. I use a matrix to store whether a substring is a palindrome, which is calculated at the beginning. The time cost is 56 ms.

    void helper(string s, vector<vector<bool>>&pali, int begin, int len, vector<string> &cur, vector<vector<string>>&res){
        if (len<=0){
            res.push_back(cur);
        }
        
        for (int i=0; i<len; i++){
            if (pali[begin][begin+i]){
                cur.push_back(s.substr(begin, i+1));
                helper(s, pali, begin+i+1, len-i-1, cur, res);
                cur.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        int len=s.size();
        vector<vector<bool> > palindrome(len, vector<bool>(len, false));
        vector<vector<string> >res;
        vector<string> tmp;
        
        for (int j=0; j<len; j++){
            for (int i=j; i<len; i++){
                palindrome[i][j]=true;
            }
        }
        
        for(int j=0; j<len; j++){
            for (int i=0; i<j; i++){
                palindrome[i][j]=((s[i]==s[j])&&(palindrome[i+1][j-1]));
            }
        }
        
        helper(s, palindrome, 0, len, tmp, res);
        return res;
        
    }

  • 0
    L

    Yes it cost less time.


Log in to reply
 

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