Skip to content

97. Interleaving String

难度:Hard

刷题内容

原题连接

  • https://leetcode.com/problems/interleaving-string/

内容描述

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

˼· **- ʱ�临�Ӷ�: O(N^2)*- �ռ临�Ӷ�: O(N^2)***

һ���ñ����ķ���ȥ�����⣬ʱ�临�Ӷ�ΪO(2^n)��ʱ�临�Ӷ�Ϊָ�������϶���ʱ内容描述ǿ����ö�̬�滮��ʱ�临�Ӷ��Ż���O(n^2)���⶯̬�滮�Ĺؼ������ҵ�״̬ת�Ʒ��̣������ά���� dp[i][j]����ʾ s1[i]�� s2[j]֮����Ӵ��Ƿ������s3[i + j]内容描述�Ǿ���д��״̬ת�Ʒ��̣�dp[i][j] = (s1[i] == s3[i + j] && dp[i + 1][j]) || (s2[j] == s3[i + j] && dp[i][j + 1])

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int l1 = s1.length(),l2 = s2.length(),l3 = s3.length();
        if(l1 + l2 != s3.length())
            return 0;
        int dp[l1 + 2][l2 + 2];
        memset(dp,0,sizeof(dp));
        dp[l1][l2] = 1;
        for(int i = l1;i >= 0;--i)
            for(int j = l2;j >= 0;--j)
            {
                if(i < l1 && s1[i] == s3[i + j] && dp[i + 1][j])
                    dp[i][j] = 1;
                if(j < l2 && s2[j] == s3[i + j] && dp[i][j + 1])
                    dp[i][j] = 1;
            }
        return dp[0][0];
    }
};


回到顶部