leetcode 随笔 Interleaving String --DP问题

本文主要是介绍leetcode 随笔 Interleaving String --DP问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Interleaving String

这是一个比较典型的动态规划问题，相似的问题有编辑距离等。不过衡量的标准从两个字符串s1与s2的匹配变成了s1s2与s3的关系匹配，相同的地方是还是进行矩阵的相关操作。

首先还是申请一块矩阵rec，矩阵的大小位n*m，其中n的大小是s1长度+1，m大小是s2长度+1，矩阵初值全为0

第一项 rec[0][0]=1

更新矩阵的第一行，每走一列就相当于匹配一位s2与s3，同理更新矩阵第一列。

除矩阵首行首列的其他位置的更新方法为

rec[i][j] = rec[i - 1][j] && s1[i - 1] == s3[i - 1 + j] || rec[i][j - 1] && s2[j - 1] == s3[i + j - 1];

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {if (s1.size() + s2.size() != s3.size()) return false;int n = s1.size() + 1, m = s2.size() + 1;bool **rec = new bool*[n];for (int i = 0; i < n; i++){rec[i] = new bool[m];memset(rec[i], 0, sizeof(bool)*m);}rec[0][0] = 1;for (int j = 1; j < m; j++){rec[0][j] = rec[0][j - 1] && s2[j - 1] == s3[j - 1];}for (int i = 1; i < n; i++){rec[i][0] = rec[i - 1][0] && s1[i - 1] == s3[i - 1];}for (int i = 1; i < n ; i++){for (int j = 1; j < m ; j++){rec[i][j] = rec[i - 1][j] && s1[i - 1] == s3[i - 1 + j] || rec[i][j - 1] && s2[j - 1] == s3[i + j - 1];}}return rec[n-1][m-1];}
};

这篇关于leetcode 随笔 Interleaving String --DP问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---