字符串的子序列

我必須編寫一個程序，它接受字符串參數s和整數參數k並打印出長度爲k的所有s序列。例如，如果我有字符串的子序列

subSequence("abcd", 3);

輸出應該是

abc abd acd bcd

我想指導。沒有代碼，請！

在此先感謝。

更新：

我想利用這個僞代碼：

Start with an empty string 
Append the first letter to the string 
    Append the second letter 
    Append the third letter 
    Print the so-far build substring - base case 
    Return the second letter 
    Append the fourth letter 
    Print the substring - base case 
Return the first letter 
    Append the third letter 
    Append the fourth letter 
    Print the substring - base case 
    Return third letter 
Append the second letter 
    Append the third letter 
    Append the fourth letter 
    Print the substring - base case 
    Return the third letter 
Return the second letter 
Append the third letter 
    Append the fourth letter 
Return third letter 
Return fourth letter 
Return third letter 
Return second letter 
Return first letter

不同的縮進表示在遞歸調用不斷深入。

（針對迭戈塞維利亞）：

按照你的建議：

private String SSet = ""; 
private String subSequence(String s, int substr_length){ 
    if(k == 0){ 
     return SSet; 
    } 
    else{ 
    for(int i = 0; i < substr_length; i++){ 
     subString += s.charAt(i); 
     subSequence(s.substring(i+1), k-1); 
    } 
    } 
    return SSet; 
} 
}

來源

2011-07-13 Nath

獨特子序列？例如給出abacd的示例 – Max

'dcb'是一個有效的序列還是必須對應於字符串參數的給定順序？ – pjwilliams

@Max：aba，abc，abd，bac，bad等。我想這個問題的描述不是很明顯，但這就是我所擁有的。 – Nath

當你有「遞歸」作爲一個標籤，我會盡力解釋你的解決方案的策略。遞歸函數應該是這樣的，你告訴一個函數：

subSequence(string, substr_length)

實際返回的（子）-strings一個Set。注意如何將問題分解爲容易遞歸的子問題。每個子序列（字符串，substr_length）應該：

從一個空的子字符串集開始，我們稱之爲SSet。
從0做一個循環的串減去substr_length
在各環位置的長度我，你把字符串[我]作爲起始字符，和調用遞歸到subSequence(string[i+1..length], substr_length - 1)（這裏..暗示的指數範圍轉換爲字符串，因此您必須使用這些索引創建子字符串）。遞歸調用subSequence將返回所有大小爲substr_length -1的字符串。你必須在所有這些子字符串前添加你選擇的字符（在這個例子中是string [i]），並將它們全部添加到SSet集合中。
只需返回構建的SSet。這一個將包含所有的子字符串。

當然，這個過程是高度優化的（例如使用動態編程來存儲長度爲i的所有子字符串），但你明白了。

來源

2011-07-13 23:16:27

我試圖製作某種僞代碼 - 請查看我的帖子的更新。 – Nath

@Nath，這可能會顯示它將如何執行，但它不是僞代碼（例如，您不顯示遞歸調用）。 –

是的，你是對的。由於我無法制作僞代碼，因此我決定從頭開始，然後嘗試根據這個步驟序列編寫僞代碼。 – Nath

所以，我看你想實現一個方法：subSequence(s, n)：它返回所有字符的字符的集合組合從長度n的s，這樣排序被保留。

本着您的願望而不是爲您提供代碼，我假設您不希望僞代碼。所以，我會以敘述性的方式解釋我的建議方法，將翻譯作爲程序性代碼作爲閱讀練習（TM）。

想想這個問題，你得到的所有字符組合位置，它可以表示爲一個位數組（a.k.a.標誌）。那麼，s="abcd"和n=3（如你的例子），所有的組合可表示如下：

1110 = abc 
1101 = abd 
1011 = acd 
0111 = bcd

注意，我們先了解一下場，所有字符都「接通」，然後轉移「關閉「位1.在n < length(s) - 1的例子中，事情變得有趣。例如，說s="abcd"和n=2。然後我們有：

1100 = ab 
1001 = ad 
1010 = ac 
0110 = bc 
0101 = bd 
0011 = cd

當你分析一個位域的子集時，遞歸就會起作用。因此，遞歸調用將減少，你有三個標誌位字段的大小和「末位淘汰」：

100 
010 
001

的大部分工作是要找到所有的位域的遞歸方法。一旦擁有它們，每個位的位置就可以用作字符數組中的索引（即s）。

這應該足以讓你開始一些僞代碼！

來源

2011-07-14 00:16:19

在他的一些評論之後，我意識到他確實在意子串的順序......所以這個解決方案不是他想要的......我編輯了我的答案， – woliveirajr

的問題正是這個：

給定一個有序集合S：{C0，C1，C2，...，CN}，導出所有有序子集 S」，S，其中，每個構件'是S的成員，且{S'：Cj，S'：Cj + 1}的相對次序等價於相對次序{S：Ci，S：Ci + d}，其中S'：Cj = S： S'：Cj + 1 = S：Ci + d。 | S |> = | S'|。

假設/斷言集合S的大小，| S |是> =子集的大小，| S'|
如果| S | - | S'| = d，那麼你知道每個子集S'以位於Si處的數字開始，其中0DDDDi。

例如給出S：{a，b，d，c}和| S'| = 3

d = 1
S」套開始 'A'（S：0），和 'b'（S：1）。

所以我們看到的問題實際上是解決d S.

的子集的長度爲3的詞法有序排列@ d = 0：獲取長度3 lopermutations爲{A，B， c，d}
@ d = 1：爲{b，c，d}獲得長度爲3的鬆弛結果
@ d = 2：d> | S | - | S'|。停。

來源

2011-07-14 00:18:02 alphazero

字符串的子序列

回答

相關問題