Leetcode 97: Interleaving String - 交錯字串

一、題目描述

給定三個字串

s1

，

s2

，

s3

， 驗證

s3

是否是由

s1

和

s2

交錯組成的。

示例

1

：

輸入

：

s1

=

“aabcc”

，

s2

=

“dbbca”

，

s3

=

“aadbbcbcac”

輸出

：

true

示例

2

：

輸入

：

s1

=

“aabcc”

，

s2

=

“dbbca”

，

s3

=

“aadbbbaccc”

輸出

：

false

二、解題思路

2.1 動態規劃

時間複雜度

空間複雜度

（

1

）

狀態定義

定義

f

［

i

］［

j

］

表示

s1

［

0

：

i

］

和

s2

［

0

：

j

］

，匹配

s3

［

0

：

i

+

j

+

1

］

（

2

）

狀態轉移方程：

dp

［

i

］［

j

］

=

（

s1

［

i

-

1

］

==

s3

［

i

+

j

-

1

］

&&

dp

［

i

-

1

］［

j

］）

||

（

s2

［

j

-

1

］

==

s3

［

i

+

j

-

1

］

&&

dp

［

i

］［

j

-

1

］）；

解釋：

<

1

>

如果

s1

的最後一個字元等於

s3

的最後一個字元，則

dp

［

i

］［

j

］

=

dp

［

i

-

1

］［

j

］；

<

2

>

如果

s2

的最後一個字元等於

s3

的最後一個字元，則

dp

［

i

］［

j

］

=

dp

［

i

］［

j

-

1

］

。

2.2 動態規劃 + 滾動陣列

時間複雜度

空間複雜度

使用一維

dp

陣列去儲存字首結果。我們利用

dp

［

i

−

1

］

的結果和

dp

［

i

］

之前的結果來計算

dp

［

i

］

，即滾動陣列。

三、C++ 程式碼

3.1 動態規劃

class

Solution

{

public

：

bool

isInterleave

（

string

s1

，

string

s2

，

string

s3

）

{

if

（

s1

。

length

（）

+

s2

。

length

（）

！=

s3

。

length

（））

return

false

；

vector

<

vector

<

bool

>>

dp

（

s1

。

length

（）

+

1

，

vector

<

bool

>

（

s2

。

length

（）

+

1

，

false

））；

for

（

int

i

=

0

；

i

<=

s1

。

length

（）；

++

i

）

{

for

（

int

j

=

0

；

j

<=

s2

。

length

（）；

++

j

）

{

if

（

i

==

0

&&

j

==

0

）

{

dp

［

i

］［

j

］

=

true

；

}

else

if

（

i

==

0

）

{

dp

［

i

］［

j

］

=

dp

［

i

］［

j

-

1

］

&&

s2

［

j

-

1

］

==

s3

［

i

+

j

-

1

］；

}

else

if

（

j

==

0

）

{

dp

［

i

］［

j

］

=

dp

［

i

-

1

］［

j

］

&&

s1

［

i

-

1

］

==

s3

［

i

+

j

-

1

］；

}

else

{

dp

［

i

］［

j

］

=

（

dp

［

i

-

1

］［

j

］

&&

s1

［

i

-

1

］

==

s3

［

i

+

j

-

1

］）

||

（

dp

［

i

］［

j

-

1

］

&&

s2

［

j

-

1

］

==

s3

［

i

+

j

-

1

］）；

}

}

}

return

dp

［

s1

。

length

（）］［

s2

。

length

（）］；

}

}；

3.2 滾動陣列

class

Solution

{

public

：

bool

isInterleave

（

string

s1

，

string

s2

，

string

s3

）

{

if

（

s1

。

length

（）

+

s2

。

length

（）

！=

s3

。

length

（））

return

false

；

vector

<

bool

>

dp

（

s2

。

length

（）

+

1

，

false

）；

for

（

int

i

=

0

；

i

<=

s1

。

length

（）；

++

i

）

{

for

（

int

j

=

0

；

j

<=

s2

。

length

（）；

++

j

）

{

if

（

i

==

0

&&

j

==

0

）

{

dp

［

j

］

=

true

；

}

else

if

（

i

==

0

）

{

dp

［

j

］

=

dp

［

j

-

1

］

&&

s2

［

j

-

1

］

==

s3

［

i

+

j

-

1

］；

}

else

if

（

j

==

0

）

{

dp

［

j

］

=

dp

［

j

］

&&

s1

［

i

-

1

］

==

s3

［

i

+

j

-

1

］；

}

else

{

dp

［

j

］

=

（

dp

［

j

-

1

］

&&

s2

［

j

-

1

］

==

s3

［

i

+

j

-

1

］）

||

（

dp

［

j

］

&&

s1

［

i

-

1

］

==

s3

［

i

+

j

-

1

］）；

}

}

}

return

dp

［

s2

。

length

（）］；

}

}；