如何获取给定字符串的所有可能的字符对？

问题描述：

我有一个字符串“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"

答

不，这是不可能的，只是因为输出尺寸基于O(n*n)。根据具体要求，它可以高达n*(n-1)或n*(n-1)/2（如果我们需要保留原始单词的顺序）。

我正在解决一个问题，我需要获得给定字符串的字符对，并且字符串的大小非常大。所以得到了超时错误。谢谢Zbynek。 – Malav

答

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。 （常量）

我可以提供一些代码，如果需要的话

映入眼帘！

感谢Syntac，正如你所说，我们需要在这里迭代所有可能的部分。那不需要O（n * n）吗？如果我在这里错了，请纠正我。 – Malav

不，你只迭代一次字符串的每个字符。没有嵌套循环或其他东西。我会给你写一些js代码。我们只需要在第二个市场二次运行时，但不是n的二次方，而是字母表的长度，这又是不变的。 – Syntac

Javascript解决方案如何适用于Java问题？ –

如何获取给定字符串的所有可能的字符对？

相关推荐