[Leetcode] 131. Palindrome Partitioning https://leetcode.com/problems/palindrome-partitioning/submissions/

cpp.cpp

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> part;
        dfs(0, s, part, result);
        return result;
    }
    void dfs(int i, string& s, vector<string>& part, vector<vector<string>>& result){
        if(i>=s.size()){
            result.push_back(part);
            return;
        }    
        for(int j = 1; (j+i) <= s.size(); j++){
            string str = s.substr(i,j);
            if(isPalindrome(str)){
                part.push_back(str);
                dfs(i+j, s, part, result);
                part.pop_back();
            }          
        }
    }
    bool isPalindrome(string& s){
        int l = 0, r = s.size() - 1;
        while(l < r){
            if(s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    }
};

ruby.rb

# @param {String} s
# @return {String[][]}
def partition(s)
    return [[s]] if s.length == 1
    result = []
    dfs(0, s, [], result)
    
    return result
end

def dfs(i, s, part, result)
    if i >= s.length
        result<<part.clone
        return
    end
    
    for j in i..s.length
        if isPalindrome?(s, i, j)
            part<<s[i..j]
            dfs(j+1, s, part, result)
            part.pop
        end
    end
end

def isPalindrome?(s, l, r)
    while l < r
        return false if s[l] != s[r]
        l, r = l+1, r-1
    end
    return true
end

https://leetcode.com/problems/palindrome-partitioning/submissions/

• C++ Score

Runtime: 115 ms, faster than 94.60% of C++ online submissions for Palindrome Partitioning.
Memory Usage: 49.2 MB, less than 96.64% of C++ online submissions for Palindrome Partitioning.

• Ruby Score

Runtime: 1909 ms, faster than 63.16% of Ruby online submissions for Palindrome Partitioning.
Memory Usage: 245.1 MB, less than 36.84% of Ruby online submissions for Palindrome Partitioning.