97. Interleaving String(Leetcode每日一题-2020.07.18)

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

Problem

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example1

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
Output: true

Example2

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
Output: false

Solution

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int m = s1.length();int n = s2.length();if(s3.length() != m+n)return false;vector<vector<bool>> f(m+1,vector<bool>(n+1));//初始化全是falses1 = " " + s1;s2 = " " + s2;s3 = " " + s3; for(int i = 0;i<=m;++i){for(int j = 0;j<=n;++j){if(!i && !j)f[i][j] = true;else{if(i && s1[i] == s3[i+j])f[i][j] = f[i-1][j];if(j && s2[j] == s3[i+j])f[i][j] = f[i][j] || f[i][j-1];}}}return f[m][n];}
};

这篇关于97. Interleaving String(Leetcode每日一题-2020.07.18)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---