用於保存多組可互換字符串的數據結構

我有一組字符串。其中，2個或更多的組可能代表相同的事物。這些組應該以給定組中任何成員的方式存儲，您可以高效率地獲取組中的其他成員。用於保存多組可互換字符串的數據結構

因此給定這個初始集合：["a","b1","b2","c1","c2","c3"]結果結構應該類似["a",["b1","b2"],["c1","c2","c3"]]而Fetch（「b」）應該返回["b1","b2"]。

爲此目的，是否存在特定的數據結構和/或算法？

編輯：「b1」和「b2」不是實際的字符串，它們表示2屬於同一組。否則Trie會是一個完美的選擇。

來源

2011-12-31 parsa

它是一個特定的編程語言編程問題嗎？如果不是這可能屬於計算機科學堆棧交換而不在這裏。如果你確實參考了一個特定的編程問題和語言，請編輯accordinagly – alonisser 2011-12-31 16:53:23

聽起來像[不相交集森林]（http://en.wikipedia.org/wiki/Disjoint-set_data_structure），但向後... – 2011-12-31 16:59:06

你會顯示你的確切的問題，目前不明確你的團隊是什麼？ – 2011-12-31 17:35:01

我可能會誤解最初的問題設置，但我相信對於使用現成數據結構的這個問題有一個簡單而優雅的解決方案。這個想法在很大程度上是從字符串到字符串集創建一個映射。地圖中的每個鍵都將與它等於的一組字符串相關聯。假設組中的每個字符串映射到相同的一組字符串，這可以在時間和空間上高效完成。

的算法可能會是這樣的：

構建從字符串的地圖M至琴絃組。
將所有字符串分組在一起，彼此相等（這一步取決於字符串和組的指定方式）。
對於每個羣集：
1. 在該羣集中創建一個規範的字符串集合。
2. 將每個字符串添加到映射中，作爲其值爲規範集的鍵。

該算法和結果數據結構相當有效。假設你已經預先知道了這個簇，這個過程（使用一個trie作爲映射的實現和一個簡單的列表作爲這個集合的數據結構）需要你訪問每個輸入字符串的每個字符恰好兩次 - 一次插入當它被添加到與它相同的字符串集合中時，它會被加入到trie中，並且假設您正在進行深層複製。因此這是一個O（n）算法。另外，查找速度非常快 - 找到等於某個字符串的字符串集合，只需遍歷字典查找字符串，查找相關聯的字符串集合，然後遍歷它即可。這需要O（L + k）時間，其中L是字符串的長度，k是匹配的數量。

希望這有幫助，並讓我知道如果我誤解了問題陳述！

來源

2011-12-31 20:16:55 templatetypedef

既然這是Java，我會用HashMap<String, Set<String>>。這將映射每個字符串到它的等價集合（將包含該字符串和屬於同一個組的所有其他字符串）。你如何從輸入構造等價集取決於你如何定義「等價」。如果輸入是爲了按組（但實際上沒有進行分組），如果你有一個謂語實現測試等價，你可以做這樣的事情：

boolean differentGroups(String a, String b) { 
    // equivalence test (must handle a == null) 
} 

Map<String, Set<String>> makeMap(ArrayList<String> input) { 
    Map<String, Set<String>> map = new HashMap<String, Set<String>>(); 
    String representative = null; 
    Set<String> group; 
    for (String next : input) { 
     if (differentGroups(representative, next)) { 
      representative = next; 
      group = new HashSet<String>(); 
     } 
     group.add(next); 
     map.put(next, group); 
    } 
    return map; 
}

注意的是，如果集團這隻能是連續的輸入中的元素。如果他們不是，你需要更復雜的簿記來建立組織結構。

來源

2011-12-31 23:28:59

用於保存多組可互換字符串的數據結構

回答

相關問題