Java - überprüfen ob ein Zeichen 2x in einem String

[darph]

... vorkommt. Oder generell mehrfach...

Wie kann ich elegant überprüfen, ob ein Zeichen in einem String mehr als einmal vorkommt?

[darph]

private static boolean isSane(String s) {

int count = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < s.length(); j++) {

if (s.charAt(i) == s.charAt(j)) {
count++;
}
}
}
return (count == s.length());
}

Hat jemand was schöneres? ;(

[Dr.Doom]

Schöner? Keine Ahnung - höchstens anders. ;)

Anstatt zwei Schleifen, kannst du's mir einer probieren und dann für jedes Zeichen des Strings 'int lastIndexOf(int char)' abfragen.
Bei einer Ungleichheit hast du mindestens ein Zeichen, das mindestens zweimal im String vorhanden ist.

EDIT:

private static boolean isSane(String s) {

for (int i = 0; i < s.length(); i++) {
if (i != lastIndexOf(s.charAt(i)) {
return false; // doppeltes Zeichen gefunden
}
}
return true; // keine doppelten Zeichen
}

Ohne Gewähr. ;)

[darph]

:O

Duz ist gut!

Danke. :)

[MadMan2k]

wobei du in String.lastIndexOf() die Schleife doch wieder drin hast ;)

[darph]

wobei du in String.lastIndexOf() die Schleife doch wieder drin hast ;)
Aber es ist trotzdem im Schnitt billiger (Wenn es ein Zeichen mehrfach gibt), weil die Methode abbricht, sobald ein doppeltes Zeichen gefunden wurde.

Meine Methode geht ganz durch und überprüft dann, ob nicht bei einem Zeichen 2x count++ gemacht wurde.

[Trap]

Asymptotisch besser ist es wenn man java.util.Set benutzt:
private static boolean isSane(String s) {
Set x = new einSet();
for (int i = 0; i < s.length(); i++) {
if(x.contains(s[i])) return false; // Boxing/Unboxing fehlt hier
x.add(s[i]); // Boxing/Unboxing fehlt hier
}
return true; // keine doppelten Zeichen
}

Andere Möglichkeit:
1. String sortieren
2. Gucken ob es ein i mit s[i].equals(s[i+1]) gibt, dann ist ein Zeichen doppelt

Beide sind in O(n log n), im Gegensatz zu O(n*n) für die bisherigen Vorschläge.

[Xmas]

Bucket Sort (für jedes mögliche Zeichen einen Zähler) wäre O(n). Aber der Overhead für Speicherreservierung und 0-Setzen lohnt bei kurzen Strings nicht.

[Trap]

Bucket Sort ist bei Unicode-Strings deutlich schlechter geeignet als bei 8-byte-char strings.

Java hat Unicode-Strings...

[Xmas]

Man kann es immer noch in mehrere Phasen aufteilen.

[darph]

X-D

Okay.

Ich hab mal gebencht: Meine (a) und dr.dooms (b) Methoden :

Zunächst mal mit folgendem String (keine doppelten):
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvxyz1234567890!§$%&/()=?´`ßöäüÖÄÜ,.-_:;<>°^"

-----------
Overall Time (1000 checks):
a 2121
b 432
-----------
Overall Time (1000 checks):
a 2183
b 331
-----------
Overall Time (1000 checks):
a 1952
b 572
-----------
Overall Time (1000 checks):
a 2012
b 461
-----------
Overall Time (1000 checks):
a 2024
b 470
-----------
Overall Time (1000 checks):
a 2152
b 351
-----------
Overall Time (1000 checks):
a 2103
b 411
-----------
Overall Time (1000 checks):
a 2104
b 370
-----------
Overall Time (1000 checks):
a 2083
b 360
-----------
Overall Time (1000 checks):
a 2064
b 530
true



Dann mit diesem String (ein doppelter):
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvxyz1234567890!§$%&/()=?´`ßöaäüÖÄÜ,.-_:;<>°^";

-----------
Overall Time (1000 checks):
a 2304
b 260
-----------
Overall Time (1000 checks):
a 2254
b 160
-----------
Overall Time (1000 checks):
a 2163
b 220
-----------
Overall Time (1000 checks):
a 2163
b 210
-----------
Overall Time (1000 checks):
a 2064
b 270
-----------
Overall Time (1000 checks):
a 2183
b 190
-----------
Overall Time (1000 checks):
a 2174
b 180
-----------
Overall Time (1000 checks):
a 2213
b 170
-----------
Overall Time (1000 checks):
a 2253
b 161
-----------
Overall Time (1000 checks):
a 2273
b 210
false


eh.. vertippt. Sind natürlich 10'000 Checks pro durchlauf und nicht nur tausend.

Die Aussage von MadMan2k mag zwar stimmen, aber trotzdem ist dr.dooms Methode schneller.

Andererseits: Es geht um eine Enigma. Die hat vielleicht 5 Walzen, und bei 5 Checks ist beides nach allerhöchstens 1 Millisekunde fertig. X-D


Interessant wird es also erst, wenn man eine Enigma für Chinesisch basteln will. ;(