查找按字符索引分組的多個字符串的聯合算法

我一直在試圖想到一種性能高效的方式來查找按索引分組的字符集中字符出現的聯合。像這樣的東西;查找按字符索引分組的多個字符串的聯合算法

s1 = "013965" 
s2 = "015935" 
s3 = "310012"

在下面的每個數字組中的所有字符串的字符指數n存在所得：

out = "[03][1][350][90][631][52]"

我已經想到了做這件事通過每個字符串迭代的非常簡單的方式，在每一個索引，同時將中間字符串存儲在數組中，然後迭代該數組以構建輸出值。然而，我認爲我的方法是一種非常低效的方式，與漸近最優解決方案相距甚遠。

來源

2014-02-13 pondigi

通常情況下，最好是讓事情在功能上正確無誤，然後在獲得工作解決方案後再擔心性能問題。在做事情的時候，這種天真的方式經常幫助你看到可以輕鬆獲得收益的地方。 – Durandal

Google'profile matrix bioinformatics'。可能會給你一些想法。 –

我認爲你不可能比天真的方式做得更好，因爲通常你需要檢查所有字符串的所有位置（除非在位置k，所有數字0-9都已經發生）。想象一下，你所有的字符串都以4開頭，最後一個字符串以5開頭，然後你需要遍歷所有字符串的0位置，以免錯過最後一個字符串的5（與其他位置不同）。這同樣適用於每個職位。 –

如果設定的所有可能的字符是預先知道的，比方說，他們的人數是n，與n是不是過高（例如10，如果你做的只是個數字），你可以通過創建m布爾做到這一點長度爲n的數組，其中m是位置或輸入字符串中的數字以及n的數字。如果第n個字符出現在任何輸入字符串中的第m個位置，則第m個數組中的第n個位置將是true。 False將表示，沒有這樣的角色在之前的第m位置。

然後就可以遍歷每個字符串，而當你在位置遇到字符nm你標記在第m個陣列的第n個位置向下true。在結束時，你將有m陣列，每個描述的第m組

pos[0] = {true, true, false, false, false, true, true, false, true, false} 
pos[1] = {true, false, false, false, false, false, false, false, false, false} 
pos[2] = {false, false, true, true, false, false, false, false, false, true}

內容轉換爲

[0,1,5,6,8] [0] [2,3,9]

由於所有的結構是直接訪問陣列，沒有涉及查找，所有的訪問都是不變的，你只需要訪問每個角色一次，不需要比較。希望這可以幫助。

來源

2014-02-13 21:48:18 Warlord

第二個組應該是[0]，第三個[2,3,9]根據數據轉換在第一組完成 –

謝謝，我的不好 – Warlord

查找按字符索引分組的多個字符串的聯合算法

回答

相關問題