With 26 / 28 test cases passed. I cannot find my method's fault.


  • 0
    C

    About my method, firstly i took the source string for DP anlysis.
    Then, took Recursive for the string to find the longest substring of Palindrome.
    But ,Unfortunately, my method stopped at the case: "apjesgpsxoeiokmqmfgvjslcjukbqxpsobyhjpbgdfruqdkeiszrlmtwgfxyfostpqczidfljwfbbrflkgdvtytbgqalguewnhvvmcgxboycffopmtmhtfizxkmeftcucxpobxmelmjtuzigsxnncxpaibgpuijwhankxbplpyejxmrrjgeoevqozwdtgospohznkoyzocjlracchjqnggbfeebmuvbicbvmpuleywrpzwsihivnrwtxcukwplgtobhgxukwrdlszfaiqxwjvrgxnsveedxseeyeykarqnjrtlaliyudpacctzizcftjlunlgnfwcqqxcqikocqffsjyurzwysfjmswvhbrmshjuzsgpwyubtfbnwajuvrfhlccvfwhxfqthkcwhatktymgxostjlztwdxritygbrbibdgkezvzajizxasjnrcjwzdfvdnwwqeyumkamhzoqhnqjfzwzbixclcxqrtniznemxeahfozp".
    Can AnyOne Help Me!

    class Solution {
    public:
    	int minCut(string s) {
    		vector<bool> tmp(s.size(), false);
    		vector<vector<bool>> dp(s.size(), tmp);
    		createDp(dp, s);
    
    		int cnt = getMinCut(s, dp, 0, s.size() - 1);
    
    		return cnt - 1;
    	}
    private:
    
    	int getMinCut(const string& s, const vector<vector<bool>>& dp, int begin, int end)
    	{
    		int num;
    		if (begin > end)
    			num = 0;
    		else if (begin == end)
    			num = 1;
    		else
    		{
    			vector<int> loc = getMaxLengthPalindrome(dp, begin, end);
    			if (loc[1] - loc[0] == end - begin)
    			{
    				num = 1;
    			}
    			else
    			{
    				num = 1 + getMinCut(s, dp, begin, loc[0] - 1) + getMinCut(s, dp, loc[1] + 1, end);
    			}
    		}
    		return num;
    	}
    
    	vector<int> getMaxLengthPalindrome(const vector<vector<bool>>& dp, int begin, int end)
    	{
    		int maxlen = -1;
    		int begin1, end1;
    		for (int i = begin; i <= end; ++i)
    		{
    			for (int j = i; j <= end; ++j)
    			{
    				if (dp[i][j] && j - i > maxlen)
    				{
    					maxlen = j - i;
    					begin1 = i;
    					end1 = j;
    				}
    
    			}
    		}
    		vector<int> result = { begin1, end1 };
    		return result;
    	}
    
    	void createDp(vector<vector<bool>>& dp, string s)
    	{
    		for (int i = s.size() - 1; i >= 0; --i)
    		{
    			for (int j = i; j < s.size(); ++j)
    			{
    				if (i == j)
    					dp[i][j] = true;
    				else
    				{
    					if (s[i] == s[j])
    					{
    						if (j == i + 1 || dp[i + 1][j - 1])
    							dp[i][j] = true;
    					}
    				}
    			}
    		}
    	}
    
    };

  • 0
    S

    Have you ever noticed this words Writing code? Select a code block and click on the {} button to preserve code formatting. above your text editor?


Log in to reply
 

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