Am I doing something redundant?


#1
vector<vector<string>> answer;
vector<string> temp;

bool checkPalindrome(string A)
{
    for(int i=0,j=A.size()-1;i<j;i++,j--)
    {
        if(A[i]!=A[j])
            return false;
    }
    return true;
}

void createPartitions(string A, int index)
{
    if(index==A.size())
    {
        //process the paritioning, stored in temp
        int flag=0;
        for(auto x:temp)
            if(!checkPalindrome(x))
            {    
                flag=1;
                break;
            }
        if(flag)
            ;
        else
            answer.push_back(temp);
    }
    else
    {
        for(int i=1;i+index<=A.size();i++)
        {
            temp.push_back(A.substr(index,i));
            createPartitions(A,index+i);
            temp.pop_back();
        }
    }
}


vector<vector<string> > Solution::partition(string A) {
    createPartitions(A,0);
    auto x=answer;
    answer.clear();
    temp.clear();
    return x;
    
}


#2

@shoumikg,

You can avoid checking the same string for palindrome if already checked by hashing the already checked string.

bool checkPalindrome(string str, unordered_map<string, bool> &palindrome_mp)
{
    if(palindrome_mp.find(str) != palindrome_mp.end())
    {
        return palindrome_mp[str];
    }
    
    int i = 0, j = str.length() - 1;
    bool isPalindrome = true;
    
    while(i < j)
    {
        if(str[i] != str[j])
        {
            isPalindrome = false;
            break;
        }
        
        i++;
        j--;
    }
    
    palindrome_mp.insert(make_pair(str, isPalindrome));
    
    return isPalindrome;
}
 
void partitionUtil(unordered_map<string, bool> &palindrome_mp, vector<vector<string> > &res, string A, vector<string> &partitions, int index)
{
    if(index == A.length())
    {
        bool isAllPalindrome = true;
        
        for(string str: partitions)
        {
            if(!checkPalindrome(str, palindrome_mp))
            {
                isAllPalindrome = false;
                break;
            }
        }
        
        if(isAllPalindrome)
        {
            res.push_back(partitions);
        }
        
        return;
    }
    
    for(int i = 1; i + index <= A.length(); i++)
    {
        partitions.push_back(A.substr(index, i));
        partitionUtil(palindrome_mp, res, A, partitions, index + i);
        partitions.pop_back();
    }
}
 
vector<vector<string> > Solution::partition(string A) {
   vector<vector<string> > res;
   vector<string>partitions;
   unordered_map<string, bool>palindrome_mp;
   
   partitionUtil(palindrome_mp, res, A, partitions, 0);
   
   
   return res;
}

#3

Thanks man! That’s pretty sweet.