[LeetCode]一般化された略語

Generalized Abbreviation

単語の一般化された略語を生成する関数を記述します。

例：
与えられた単語= '語' 、次のリストを返します（順序は関係ありません）：

['word', '1ord', 'w1rd', 'wo1d', 'wor1', '2rd', 'w2d', 'wo2', >'1o1d', '1or1', 'w1r1', '1o2', '2r1', '3d', 'w3', '4']

分析

この質問の最初のステップを理解する必要があります。最初に考慮すべきことは、そこにいくつの結果があるかということです。よく見ると、最終的にCn0 + Cn1 + Cn2 + ... + Cnn = 2 ^ nの結果が得られることがわかります。
次に、再帰によって現在の結果が保存されるたびにDFSを使用する必要があることは明らかです。その後、DFSを続行します。次のDFSの開始位置は、現在の終了位置から分離する必要があることに注意してください。そうしないと、連続した番号の結果が発生します。連続番号が期待されない理由は、連続番号を1つの番号に結合できるためです。これはすでにカウントされています。 Ab111はab3であり、必要な結果はab3です。

複雑さ

時間：O（2 ^ n）、スペース：O（n）

コード

public class Solution { public List generateAbbreviations(String word) { List res = new ArrayList() dfs(res, '', 0, word) return res } public void dfs(List res, String curr, int start, String s) { res.add(curr + s.substring(start)) if (start == s.length()) return / / Define a new starting position int i = 0 // except for the beginning, the starting position must be separated from the previous ending position if (start > 0) { i = start + 1 } for ( i