給定一個包含字符的數組的數組，找到至少有一個公共字符的所有數組，並將它們作爲對返回

Question

蠻力法將 1.將每個數組與另一個數組進行比較 2.如果有1個公共字符;打印該對 時間：O（n3）

我們將如何優化？

Answer 1

讓字符爲ASCII。這樣的可能的字符數爲256

實施例：

your_array = [['abc'], ['dxf'], ['xyz'], ['axd']] 

允許，indices[256]是陣列，其中indices[i]將包含那些誰與ASCII碼i一個字符數組的索引的陣列。

indices[97] = [0, 3] // ascii code a is 97 
indices[98] = [0] // as 
indices[99] = [0] 
indices[100] = [1, 3] 
indices[120] = [1, 2, 3] 
indices[102] = [1] 
indices[121] = [2] 

現在，生成從那裏size(indices) > 1

For indices[97] 

pairs: 
<['abc'], ['axd']> 

...... 

...... 

...... 

For indices[120] 

pairs: 
<['dxf'], ['xyz']> 
<['dxf'], ['axd']> 
<['xyz'], ['axd']> 

的空間複雜度是O(n)其中n是字符數組的數量各索引的對。

構建indices陣列的時間複雜度爲O(n)，並且在最差的情況下打印所有對的數量爲O(n^2)。但是，由於打印所有對（產出輸出）對於該問題是強制性的，所以這種複雜性是無法考慮的。

Answer 2

如果我理解正確的問題，這是可以解決的方式如下：

1. 每一個字符爲每個陣列的計數appearences並建立總數爲沿途每個字符。

2. 迭代數組的字符數並從總數中減去它，如果至少一個計數大於0，則數組有效。

因爲字符的數目是恆定的（1個字節= 256）它是O（n * m），其中n是字符的總數量，M陣列的數量。