leetcode补全计划-20180806

1. 132 Palindrome Partitioning II
   输入：字符串
   输出：数字
   要求：该数字是将字符串切割成回文子串的最小切割数。
   思路：动态规划。根据每个字符分别考虑以该字符为中心的偶数回文串的情况以及奇数回文串的情况。

class Solution {
public:
    int minCut(string s) {
        int size = s.size();
        vector<int> tool(size + 1, 0);
        for(int i = 0;i <= size;++ i) tool[i] = i - 1;
        for(int i = 0;i < size;++ i){
            for(int j = 0;i - j >= 0 && i + j < size && s[i - j] == s[i + j];++ j)
                tool[i + j + 1] = min(tool[i + j + 1], tool[i - j] + 1);
            for(int j = 0;i - j + 1 >= 0 && i + j < size && s[i - j + 1] == s[i + j];++ j)
                tool[i + j + 1] = min(tool[i + j + 1], tool[i - j + 1] + 1);
        }
        return tool[size];
    }
};

2. 87 Scramble String
   输入：字符串s1和s2
   输出：bool
   要求：判断s1和s2是否存在scrambled关系
   思路：DFS，递归出口是s1==s2

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1 == s2) return true;
        int size = s1.size();
        int tool[26] = {0};
        for(auto a : s1) tool[a - 'a'] ++;
        for(auto a : s2) tool[a - 'a'] --;
        for(auto a : tool) if(a != 0) return false;
        for(int i = 1;i < size;++ i){
            if(isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i))) return true;
            if(isScramble(s1.substr(0,i), s2.substr(size - i)) && isScramble(s1.substr(i), s2.substr(0, size - i))) return true;
        }
        return false;
    }
};

3. 72 Edit Distance
   输入： 字符串word1和word2
   输出： 数字
   条件： 题目允许对word1进行以下三种操作：插入一个字母、删除一个字母、替换一个字母。给出将word1变为word2的最少操作次数
   思路： 动态规划。构造最常用的二维数组，然后按位进行思考。分为i位置的word1对应字母和word2的对应字母是否相等两种情况进行考虑。

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

4. 10 Regular Expression Matching
   输入：目标字符串s和模式字符串p
   输出：bool
   条件：p中. 对应任一字符.*和前面一个字符一起对应0个活多个前一字符。给出判断：p是否能匹配s。
   思路：动态规划。构建最常用的二维动态规划数组，以p串中i位置的字符是否是*为基准进行考虑。

class Solution {
public:
    bool isMatch(string s, string p) {
        int s_size = s.size();
        int p_size = p.size();
        vector<vector<int>> tool(p_size + 1, vector<int>(s_size + 1, 0));
        tool[0][0] = 1;
        for(int i = 1;i <= p_size;++ i) tool[i][0] = i > 1 && p[i - 1] == '*' && tool[i - 2][0];
        for(int i = 1;i <= p_size;++ i) for(int j = 1;j <= s_size;++ j){
            if(p[i - 1] == '*'){
                tool[i][j] = tool[i - 2][j] || tool[i][j - 1] && (p[i - 2] == '.' || p[i - 2] == s[j - 1]);
            }else{
                tool[i][j] = (s[j - 1] == p[i - 1] || p[i - 1] == '.') && tool[i - 1][j - 1];
            }
        }
        // for(auto a : tool){
        //     for(auto b : a) cout<<b<<' ';
        //     cout<<endl;
        // }
        return tool[p_size][s_size];
    }
};