Problem
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false
Solution: DP
Subproblems : whether s3[0:i+j] can be formed by interleaving s1[0:i] and s2[0:j].
Time complexity: O(mn)
Space complexity: O(mn)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huhaua // Running time: 0 ms class Solution { public: bool isInterleave(string s1, string s2, string s3) { int l1 = s1.length(); int l2 = s2.length(); int l3 = s3.length(); if (l1 + l2 != l3) return false; // dp[i][j]: whehter s3[0:i+j] is a interleva of s1[0:i] and s2[0:j] vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1)); dp[0][0] = true; for (int i = 0; i <= l1; ++i) for (int j = 0; j <= l2; ++j) { if (i > 0) dp[i][j] |= dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]; if (j > 0) dp[i][j] |= dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]; } return dp[l1][l2]; } }; |
Recursion + Memorization
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 0 ms class Solution { public: bool isInterleave(string s1, string s2, string s3) { m_ = vector<vector<int>>(s1.length() + 1, vector<int>(s2.length() + 1, INT_MIN)); return dp(s1, s1.length(), s2, s2.length(), s3, s3.length()); } private: // m_[i][j]: whehter s3[0:i+j] is a interleva of s1[0:i] and s2[0:j] vector<vector<int>> m_; bool dp(const string& s1, int l1, const string& s2, int l2, const string& s3, int l3) { if (l1 + l2 != l3) return false; if (l1 == 0 && l2 == 0) return true; if (m_[l1][l2] != INT_MIN) return m_[l1][l2]; if (l1 > 0 & s3[l3 - 1] == s1[l1 - 1] && dp(s1, l1 - 1, s2, l2, s3, l3 - 1) ||l2 > 0 & s3[l3 - 1] == s2[l2 - 1] && dp(s1, l1, s2, l2 - 1, s3, l3 - 1)) m_[l1][l2] = 1; else m_[l1][l2] = 0; return m_[l1][l2]; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment