如何獲取給定字符串的所有可能的字符對？

我有一個字符串「oracle」。我想獲得應用程序可能的字符對。我嘗試過這樣做，並能夠在o(n*n)中做到這一點。我正在尋找更優化的解決方案。我們能解決它在不到o(n*n)？如何獲取給定字符串的所有可能的字符對？

Input : oracle 
Output : "or" "oa", "oc", "ol", "oe" , "ra", "rc", "rl", "re" , "ac", "al", "ae", "cl", "ce", "le"

來源

2016-10-08 Malav

不，這是不可能的，只是因爲輸出尺寸基於O(n*n)。根據具體要求，它可以高達n*(n-1)或n*(n-1)/2（如果我們需要保留原始單詞的順序）。

來源

2016-10-08 03:39:34

我正在解決一個問題，我需要獲得給定字符串的字符對，並且字符串的大小非常大。所以得到了超時錯誤。謝謝Zbynek。 – Malav

-1

String string = "oracle"; 
    HashMap occurs = new HashMap(); 

    for(int i=0; i<string.length(); i++) 
     occurs.put(""+string.charAt(i), new Boolean(true)); 

    for(char a='a'; a < 'z'; a++) 
     if(occurs.get(""+a)!=null) 
      for(char b=(char) (a+1); b<'z'; b++) 
       if(occurs.get(""+b)!=null) 
        System.out.print(a+""+b+" ");

這是可能的線性時間。
首先，您需要一個布爾型數組（！用於常量查找時間）字母表中的所有字符，並遍歷字符串以檢查包含哪些字符。其次，你需要遍歷所有可能的字符對，並檢查兩個字符是否包含，如果相應的布爾值是true。 （常量）

我可以提供一些代碼，如果需要的話

映入眼簾！

來源

2016-10-08 03:44:59 Syntac

感謝Syntac，正如你所說，我們需要在這裏迭代所有可能的部分。那不需要O（n * n）嗎？如果我在這裏錯了，請糾正我。 – Malav

不，你只迭代一次字符串的每個字符。沒有嵌套循環或其他東西。我會給你寫一些js代碼。我們只需要在第二個市場二次運行時，但不是n的二次方，而是字母表的長度，這又是不變的。 – Syntac

Javascript解決方案如何適用於Java問題？ –

如何獲取給定字符串的所有可能的字符對？

回答

相關問題