如何最大限度地發揮，而不考慮單詞的列表共性

相乘的兩個字符串長度的結果，發現兩個字符串S和T這樣的：如何最大限度地發揮，而不考慮單詞的列表共性

S和T沒有共同的性格
S.length() * T.length()是最大化

我的做法是，首先爲每個字符串構建位圖，並試圖找到最大乘數。你能給我一個更好的算法，其時間複雜度小於O（n ）？

public class biggest_multiply { 
    int biggest(String[] array){ 
     if(array==null||array.length<=1) 
      return 0; 
     class bitMap{ 
      int bit; 
      String s; 
     } 
     bitMap[] bm=new bitMap[array.length]; 
     for(int i=0;i<array.length;i++){ 
      bm[i]=new bitMap(); 
      for(int j=0;j<array[i].length();j++) 
       bm[i].bit=bm[i].bit|(1<<(array[i].charAt(j)-'a')); 
      bm[i].s=array[i]; 
     } 
     int maximum=0; 
     for(int i=0;i<array.length;i++){ 
      for(int j=i+1;j<array.length;j++) 
       if((bm[i].bit&bm[j].bit)==0) 
        maximum=Math.max(maximum, bm[i].s.length()*bm[j].s.length()); 
     } 
     return maximum; 
    } 
    public static void main(String[] args){ 
     System.out.println(new biggest_multiply().biggest(new String[]{"aa","aabb","bb","cc"})); 
    } 
}

來源

2013-11-22 Lampard

至少嘗試一下你自己的家庭作業問題。 – chrylis

這不是一項家庭作業..我在網上看到它，並認爲這是一個有趣的問題。我只能想到爲每個字符串的字符做hashset或bitmap並逐一比較。然而，找到最大化的乘法結果成本O（n^2）... – Lampard

這是一個艱難的。元素清晰度問題告訴我們，我們無法確定兩個單詞是否沒有比O（m lg m）時間更好的共同字符（假設平均字長爲m）。也許有一個更好的算法來攤銷的情況下，但我不知道任何。我們可以使用一個散列表爲O（m）時間「破壞」這個邊界，但假設一個恆定時間散列函數等。 –

-1

甲直接的解決方案是嘗試S中&詞語的每一個可能的匹配T的運行時間將是O（N * m），其中n是單詞和米的數量是一個字的大小。

更好的方法是預先計算每個單詞中的字符映射和迭代之前的大小。運行時間將減少到O（n）。

來源

2013-11-22 04:43:38

不會嘗試每個可能的單詞匹配爲O（n^2 m^2）？迭代所有單詞一次將是O（nm）。然後爲每個單詞添加一個字符映射，然後將其減少到O（n^2 m）。該解決方案似乎與用戶在其上面評論中所建議的相同。 –

嘗試每個可能的單詞匹配的時間複雜度是O（n^2 m^2）.. – Lampard

按word.length（）降序對單詞進行排序，因此可以加快短路。但還是O（n^2）。

if (bm[i].s.length() * bm[j].s.length() <= max) 
    break; 

if ((bm[i].bit & bm[j].bit)==0) { 
    maximum=Math.max(maximum, bm[i].s.length()*bm[j].s.length()); 
    break; 
}

來源

2014-01-12 03:36:52 lichgo

如何最大限度地發揮，而不考慮單詞的列表共性

回答

相關問題