力扣刷题记录（25）LeetCode：583、72、647

583.?两个字符串的删除操作

题目说可以删除任意一个字符串中的字符，实际上就是在求两个字符串的公共子序列。求得公共子序列后与字符串长度做个减法即可得需要的步数。

class Solution {
public:
    //求最长子数组
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        int maxLength=0;
        for(int i=1;i<=word1.size();i++)
        {
            for(int j=1;j<=word2.size();j++)
            {
                if(word1[i-1]==word2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                maxLength=max(maxLength,dp[i][j]);
            }
        } 
        return word1.size()+word2.size()-2*maxLength;
    }
};

72.?编辑距离

?这题还是分两种情况来写递推公式，当前字符相等或者不相等

示例：word1="horse"? word2="ros"

1.当前字符相等

? ? ? ? 比如说ho、ro，此时字符就相等，那么所需的操作步数就等于前一个字符所需要的步数，因为当前字符已经相等不需要对它进行操作。即dp[i][j]=dp[i-1][j-1]

2.当前字符不相等

? ? ? ? 可以对当前字符进行3中操作

• 替换

? ? ? ? 比如hor、ros，此时就可以将r直接替换成s，dp[i][j]=dp[i-1][j-1]+1

• 删除

? ? ? ? 比如hor、ro，此时就可以将r直接删除，dp[i][j]=dp[i-1][j]+1

• 增加

? ? ? ? 比如ho、ros，此时就可以添加一个s，dp[i][j]=dp[i][j-1]+1

? ? ?综上，当前字符不相等时，dp[i][j]=min( dp[i-1][j-1] , dp[i-1][j] , dp[i][j-1] ) +1?

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i=0;i<=word1.size();i++)
        {
            dp[i][0]=i;
            
        }
        for(int j=0;j<=word2.size();j++)
        {
            dp[0][j]=j;
        }
        for(int i=1;i<=word1.size();i++)
        {
            for(int j=1;j<=word2.size();j++)
            {
                if(word1[i-1]==word2[j-1])
                    dp[i][j]=dp[i-1][j-1];
                else
                    dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

647.?回文子串

方法一：暴力求解

class Solution {
public:
    bool huiwen(string s,int start,int end)
    {
        while(start<end)
        {
            if(s[start]!=s[end])
                return false;
            start++;
            end--;
        }
        return true;
    }
    int countSubstrings(string s) {
        int ans=1;
        for(int i=1;i<s.size();i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(huiwen(s,j,i))
                    ans++;
            }
        }
        return ans;
    }
};

?方法二：动态规划

用i、j表示s的索引，dp[i][j]表示区间[j,i]内的字符串是否是回文串。如果s[i]==s[j]，那么我们只需要看dp[i-1][j+1]是否是回文串。如果s[i]!=s[j]，那么dp[i][j]=false

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
        int ans=0;
        for(int i=0;i<s.size();i++)
        {
            for(int j=i;j>=0;j--)
            {
                if(s[i]==s[j])
                {
                    if(i-j<2 || dp[i-1][j+1]==true)
                    {
                        dp[i][j]=true;
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};