查找合併兩個字符串形成的最小詞彙字符串

假設我們給出了兩個字符串s1和s2（均爲小寫字母）。我們有兩個找到可以通過合併兩個字符串形成的最小詞彙字符串。查找合併兩個字符串形成的最小詞彙字符串

在開始時，它看起來很簡單，因爲合併了mergesort算法。但讓我們看看會出現什麼問題。

S1：ZYY

S2：ZY

現在，如果我們執行這兩個合併，我們必須決定選擇其中Z，因爲他們是平等的，很明顯，如果我們選擇，然後串形成的S2第一Z-將是：

zyzyy

如果我們選擇的z s1第一個，形成將是字符串：

zyyzy這是正確的。

正如我們可以看到mergesort的合併可能導致錯誤的答案。

再舉一例：

S1：ZYY

S2：ZYB

現在正確答案將是zybzyy這將得到只有S2首先挑ž。

還有很多其他情況下簡單的合併將失敗。我的問題是有沒有用於執行此類輸出合併的任何標準算法。

來源

2016-02-08 Sumeet Singh

你究竟如何合併這兩個字符串？每一步你從其中一個人開始彈出一個角色？ – svs

@svs從兩個字符串的左邊開始，選擇較小的字符。 –

問題在於它只是合併排序的合併操作。合併排序的前提是您的子列表已經排序。你的字符串沒有排序，因此問題。 – dhke

您可以使用動態編程。在f[x][y]中存儲最小的詞典字符串，以便您從s2的第一個字符串s1和y中挑選x個字符。您可以使用更新按照從下往上的方式計算f：

f[x][y] = min(f[x-1][y] + s1[x], f[x][y-1] + s2[y]) \\ the '+' here represents 
                \\ the concatenation of a 
                \\ string and a character

你開始f[0][0] = "" (empty string)。

爲了提高效率，您可以將字符串作爲參考存儲在f中。也就是說，你可以在f存儲對象

class StringRef { 
    StringRef prev; 
    char c; 
}

要提取你有什麼串在某些f[x][y]您只需按照引用。爲了達到目的，您可以指回f[x-1][y]或f[x][y-1]，具體取決於更新步驟所說的內容。

來源

2016-02-08 12:09:17 svs

欣賞答案，但s1和s2的長度可以增加10^5，因此我們需要不同的方法。 –

似乎解決方案可能與您所描述的幾乎相同（「mergesort」類似的方法），除了特殊處理相等。只要兩個字符串的第一個字符相同，就可以看到第二個字符，第三個等。如果某個字符串到達末尾，則將另一個字符串的第一個字符視爲字符串中的下一個字符第二個字符到達末尾等等。如果到達了兩個字符串的結尾，那麼從哪個字符串取第一個字符並不重要。注意這個算法是O(N)，因爲在相等的前綴上預讀後，你知道整個先行序列（即字符串前綴）包含，而不僅僅是一個第一個字符。

編輯：只要從兩個字符串中的當前第i個字符相等且按字母順序不大於當前前綴中的第一個字符，就會向前看。

來源

2016-02-08 12:59:09

爲什麼downvoting？任何反例？ –

查找合併兩個字符串形成的最小詞彙字符串

回答

相關問題