九章演算法 | Google 面試題：分割字串

給一個字串，你可以選擇在一個字元或兩個相鄰字元之後拆分字串，使字串由僅一個字元或兩個字元組成，輸出所有可能的結果。

線上評測地址：LintCode 領釦

樣例1

輸入： “123”

輸出： ［［“1”，“2”，“3”］，［“12”，“3”］，［“1”，“23”］］

樣例2

輸入： “12345”

輸出： ［［“1”，“23”，“45”］，［“12”，“3”，“45”］，［“12”，“34”，“5”］，［“1”，“2”，“3”，“45”］，［“1”，“2”，“34”，“5”］，［“1”，“23”，“4”，“5”］，［“12”，“3”，“4”，“5”］，［“1”，“2”，“3”，“4”，“5”］］

演算法：DFS

由於本題可以選擇在一個字元或兩個相鄰字元之後拆分字串，且最後需輸出所有可能的組合，即每次都需要把整個字串按照特定要求切分完畢，可以想到利用遞迴dfs來完成；

演算法步驟

對字串進行深度優先搜尋，當前位置達到字串末尾作為邊界。搜尋時有兩種情況：

1。 切割當前的1個字元：

將這1個字元單獨作為字串存入列表

當前位置步進1

2。 切割當前的連續2個字元（需滿足當前位置不是字串末尾）：

將連續2個字元儲存為字串存入列表

當前位置步進2

複雜度分析

時間複雜度：O（2^n）， n為字串長度

除了字串最後一位，其他位置都有兩種切割方式

空間複雜度：O（2^n^2），n為字串長度

儲存所有情況需要所有切分方式*n 的空間

public

class

Solution

{

/*

* @param ： a string to be split

* @return： all possible split string array

*/

public

List

<

List

<

String

>>

splitString

（

String

s

）

{

List

<

List

<

String

>>

result

=

new

ArrayList

<>（）；

dfs

（

s

，

0

，

new

ArrayList

<>（），

result

）；

return

result

；

}

private

void

dfs

（

String

s

，

int

index

，

List

<

String

>

current

，

List

<

List

<

String

>>

result

）

{

if

（

index

==

s

。

length

（））

{

result

。

add

（

new

ArrayList

<>（

current

））；

return

；

}

// 分割1個字元

current

。

add

（

String

。

valueOf

（

s

。

charAt

（

index

）））；

dfs

（

s

，

index

+

1

，

current

，

result

）；

current

。

remove

（

current

。

size

（）

-

1

）；

// 分割2個字元

if

（

index

<

s

。

length

（）

-

1

）

{

current

。

add

（

s

。

substring

（

index

，

index

+

2

））；

dfs

（

s

，

index

+

2

，

current

，

result

）；

current

。

remove

（

current

。

size

（）

-

1

）；

}

}

}

更多題解參考：九章演算法