[Swift]LeetCode97. 交错字符串 | Interleaving String

发布时间：2020-12-14 05:09:59 所属栏目：百科来源：网络整理

导读：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", s3 = "aadbbbaccc"Output: false 给定三个字符

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",s3 = "aadbbbaccc"
Output: false

给定三个字符串?s1,验证?s3?是否是由?s1?和?s2?交错组成的。

示例 1:

输入: s1 = "aabcc",s3 = "aadbbcbcac"
输出: true

示例?2:

输入: s1 = "aabcc",s3 = "aadbbbaccc"
输出: false

 1 // t = O(N*M),s = O(N*M)
 2 + (BOOL)isInterleaveWithS1: (NSString *)s1 s2: (NSString *)s2 s3: (NSString *)s3 {
 3     if (s1.length + s2.length != s3.length) {
 4         return false;
 5     }
 6     NSMutableArray<NSMutableArray<NSNumber *> *> *dp = [NSMutableArray arrayWithCapacity:s1.length];
 7     for (NSInteger i = 0; i < s1.length + 1; i++) {
 8         dp[i] = [NSMutableArray arrayWithCapacity:s2.length];
 9         for (NSInteger j = 0; j < s2.length + 1; j++) {
10             [dp[i] addObject:@(false)];
11         }
12     }
13     for (NSInteger i = 0; i < s1.length + 1; i++) {
14         for (NSInteger j = 0; j < s2.length + 1; j++) {
15             if (i == 0 && j == 0) {
16                 dp[i][j] = @(true);
17             } else if (i == 0) {
18                 dp[0][j] = @([dp[0][j-1] boolValue] && ([s2 characterAtIndex:j-1] == [s3 characterAtIndex:j-1]));
19             } else if (j == 0) {
20                 dp[i][0] = @([dp[i-1][0] boolValue] && ([s1 characterAtIndex:i-1] == [s3 characterAtIndex:i-1]));
21             } else {
22                 dp[i][j] = @(([dp[i][j-1] boolValue] && ([s2 characterAtIndex:j-1] == [s3 characterAtIndex:i+j-1])) || ([dp[i-1][j] boolValue] && ([s1 characterAtIndex:i-1] == [s3 characterAtIndex:i+j-1])));
23             }
24         }
25     }
26     return [dp[s1.length][s2.length] boolValue];
27 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!