Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | Scramblies |
| Level: | 5 kyu |
| Sprache: | TypeScript |
Beschreibung:
Complete the function scramble(str1, str2) that returns true if a portion of str1 characters can be rearranged to match str2, otherwise returns false.
Notes:
- Only lower case letters will be used (a-z). No punctuation or digits will be included.
- Performance needs to be considered.
* Input strings s1 and s2 are null terminated.
Examples
scramble('rkqodlw', 'world') ==> True
scramble('cedewaraaossoqqyt', 'codewars') ==> True
scramble('katas', 'steak') ==> False
Quelle: codewars.com
Lösung
Pseudo-Code
Es gibt wie immer viele Varianten, hier ist eine meiner.
Erst die Lösungsschritte in Pseudo-Code. Los geht’s:
Lösungsschritte
Schritt 1
Hier müssen wir ein bisschen auf die Performance achten. Wenn wir durch das Alphabet loopen, brauchen wir nur 26 Iterationen, das könnte klappen...
Schritt 2
Dafür können wir uns als Erstes eine Hilfsfunktion basteln, die die Anzahl eines Zeichens in einem String zählt
Schritt 3
In der Hauptfunktion brauchen wir als Erstes eine Variable mit dem Alphabet
Schritt 4
Dann der Loop durch das Alphabet
Schritt 5
Wir prüfen für jeden Buchstaben im Alphabet, ob der aktuelle Buchstabe im zweiten String öfter vorkommt als im Ersten
Schritt 6
Wenn ja, geben wir false zurück
Schritt 7
Ansonsten können wir nach dem Loop true zurückgeben
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Lösungsschritte
Die erste Zeile meiner Hilfsfunktion:
function countCharInStr(char: string, str: string): number {
Zum Zählen können wir z.B. den String am gegebenen Buchstaben bzw. Zeichen splitten und dann die Anzahl der Elemente zählen:
return str.split(char).length - 1;
}
Vom Ergebnis ziehen wir noch 1 ab. Fertig.
HINWEISDie Hilfsfunktion ist hier nicht unbedingt nötig, hilft aber bei der Lesbarkeit.
Weiter geht’s mit der Hauptfunktion.
Die erste Zeile meiner Hauptfunktion:
export function scramble(str1: string, str2: string): boolean {
Das Alphabet definieren:
const alphabet = "abcdefghijklmnopqrstuvwxyz";
Dann der Loop durchs Alphabet:
for (let letter of alphabet) {
Da wir kein i o.ä. brauchen können wir einen for...of-Loop verwenden. .forEach() ginge nicht, den können wir bei Bedarf leider nicht vorzeitig beenden.
Der Lesbarkeit halber speichere ich mir die Anzahl des aktuellen Buchstabens in str1 und str2 jeweils in einer Variablen ab:
const numLetterInStr1 = countCharInStr(letter, str1);
const numLetterInStr2 = countCharInStr(letter, str2);
Dann der Test ob in str2 mehr des aktuellen Buchstabens als in str1 sind:
if (numLetterInStr1 < numLetterInStr2) return false;
}
Wenn ja, können wir direkt false zurückgeben und damit den Loop und die Funktion vorzeitig beenden.
Ansonsten geben wir nach dem Loop true zurück:
return true;
}
Voilá! 💪
Komplettlösung
export function scramble(str1: string, str2: string): boolean {
const alphabet = "abcdefghijklmnopqrstuvwxyz";
for (let letter of alphabet) {
const numLetterInStr1 = countCharInStr(letter, str1);
const numLetterInStr2 = countCharInStr(letter, str2);
if (numLetterInStr1 < numLetterInStr2) return false;
}
return true;
}
function countCharInStr(char: string, str: string): number {
return str.split(char).length - 1;
}