在java中具有更少的空间和时间复杂度的panagram

我已经在O（n）时间和空间复杂度中实现了panagram程序。我希望我的程序的时间复杂度为O（1），空间复杂度为O（1）。在java中具有更少的空间和时间复杂度的panagram

我的步骤是：

我的字符串转换为字符数组。
将所有字符添加到树集（以避免重复）
如果树集的大小为26我打印为panagram。

有没有优化的方法可以将我的空间复杂度降低到O（1）？

2016-01-24 voidmain

[我应该在哪里张贴关于算法的问题]（http://meta.stackexchange.com/q/165519/273645）：程序员SE（http://meta.stackexchange.com/a/ 273645分之165521）。另请参阅[程序员SE常见问题解答]（https://programmers.stackexchange.com/help/on-topic），了解可以在这里提出的问题：'算法和数据结构概念'。 –

@TT。这篇文章并不反映实际的做法 - Stack Overflow比程序员得到了更多的算法问题（而不仅仅是“阻止这些代码不起作用”）（因为它应该是恕我直言 - 没有实际的标签经验想要相信）。 –

@DavidEisenstat是的，我知道，线条模糊。我只是觉得在那里得到一个好答案的机会会更好。 –

据我所知，你想检查，如果你的字符串是panagram。

如果您避免从字符串创建字符数组并从原始字符串迭代字符，则复杂度将为O（N * logA）时间和O（A）空间，其中A-字母大小。在你的情况下，A是恒定的，所以只有当你重写你的程序避免从字符串创建字符数组时，你才会有O（N）时间和O（1）空间。

P.S.不要使用树来存储字符，最好使用大小为A的数组来存储字符串中存在字符的次数。即使您可以使用大小为A的字节数组或A/8字节数来存储特定字符是否以字符串形式显示。在这个实现中，时间复杂度是O（N）而不是O（N * logA），但在复杂度估计中它并不重要，因为A是常数，但即使如此，普通数组的实现也会更快时间更快）比在树中存储字符的存在。

来源

2016-01-24 08:47:51 valdem

这里我已经修改了程序，从书中寻找字符串程序中的重复字符Cracking the coding interview您的需求使用位向量。

时间复杂度为O（n）空间复杂度为O（1）

String str = "abcdefghijklmnopqrstuvwxyz"; 
    int checker = 0; 
    for (int i = 0; i < str.length(); i++) { 
     int val = str.charAt(i) - 'a'; 
     checker |= (1 << val); 
    } 
    if (checker == 67108863)// 67108863 == 0b11111111111111111111111111 
     System.out.println("Panagram"); 
    else 
     System.out.println("Not Panagram");

来源

2016-01-24 09:02:07 Saravana

您可以通过一个位表示一个字符。

'a' -> 2^0 = 1 
'b' -> 2^1 = 2 
'c' -> 2^3 = 4 
.... 
'z' -> 2^25

然后26个字符用26位表示。

static int ALL = (1 << 26) - 1; 

public static boolean isPanagram(String s) { 
    int aggregate = 0; 
    for (int i = 0, size = s.length(); i < size; ++i) { 
     char c = Character.toLowerCase(s.charAt(i)); 
     if (c >= 'a' && c <= 'z') 
      aggregate |= 1 << (c - 'a'); 
    } 
    return aggregate == ALL; 
}

来源

2016-01-24 09:04:23 saka1029

创建字符数组需要额外的空间 – Saravana

在java中具有更少的空间和时间复杂度的panagram

回答

相关问题