從字符串中刪除字符序列

考慮一個函數，該函數接受一個字符串並返回所有可能的情況的列表，其中可以從列表中刪除三個後續的'X'。從字符串中刪除字符序列

例子：

"ABXXXDGTJXXXDGXF"應該成爲

["ABDGTJXXXDGXF", "ABXXXDGTJDGXF"]

（順序並不重要）

這裏是一個天真的實現：

f :: String -> [String] 
f xs = go [] xs [] where 
    go left (a:b:c:right) acc = 
    go (left ++ [a]) (b:c:right) y where  -- (1) 
    y = if a == 'X' && b == 'X' && c == 'X' 
     then (left ++ right) : acc 
     else acc 
    go _ _ acc = acc

我認爲主要的問題就在這裏是標有（1）的行。我通過附加到列表的左側來構建列表，這通常很昂貴。

通常這樣的事情可以通過這種模式來解決：

f [] = [] 
f (x:xs) = x : f xs

或者更明確：

f [] = [] 
f (x:right) = x : left where 
    left = f right

現在我有名單的權利並在每個遞歸離開。但是，我需要積累他們，我不知道如何在這裏做。或者我在錯誤的道路上？

溶液

靈感來自Gurkenglas'提出，這裏是有點更廣義的版本：

import Data.Bool 

removeOn :: (String -> Bool) -> Int -> String -> [String] 
removeOn onF n xs = go xs where 
    go xs | length xs >= n = 
    bool id (right:) (onF mid) $ 
    map (head mid:) $ 
    go (tail xs) 
    where 
     (mid, right) = splitAt n xs 
    go _ = [] 

removeOn (and . map (=='X')) 3 "ABXXXDGTJXXXDGXF" 
--> ["ABDGTJXXXDGXF","ABXXXDGTJDGXF"]

主要的想法似乎是以下幾點：遍歷從結尾開始列表。利用可以檢查列表的下n個元素的「預見」機制（因此如果當前列表包含那麼多元素，則必須檢查它）。通過這種遞歸遍歷，在以下元素通過真相測試的情況下，正在增強結果列表的增加。無論如何，這些結果必須添加列表的當前第一個元素，因爲它們來自較短的列表。這可以盲目地完成，因爲向結果字符串添加字符不會改變它們的匹配屬性。

來源

2016-12-24 Anton Harald

如果你有一個回答你的問題，你應該張貼它作爲一個實際的答案，而不是編輯的問題。 – user2407038

f :: String -> [String] 
f (a:b:c:right) 
    = (if a == 'X' && b == 'X' && c == 'X' then (right:) else id) 
    $ map (a:) $ f (b:c:right) 
f _ = []

來源

2016-12-24 14:49:13 Gurkenglas

解決方案似乎被硬編碼爲'XXX'作爲子字符串，這是OP想要什麼？ –

這是一個很好的答案，不幸的是沒有那麼健談。所以我試着用一些詞來解釋它，並刪除了它的硬編碼部分。它在最初的問題下添加。對此的任何評論都是值得歡迎的.. –

從字符串中刪除字符序列

回答

相關問題