Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | Typing series #1 --> the [backspace] function |
| Level: | 6 kyu |
| Sprache: | TypeScript |
Beschreibung:
This kata is a harder version of this kata: https://www.codewars.com/kata/5727bb0fe81185ae62000ae3
If you haven't done it yet, you should do that one first before doing this one.
You are given a string of letters that you need to type out. In the string there is a special function: [backspace]. Once you encounter a [backspace] , you delete the character right before it. If there is nothing to backspace , just carry on. Return the final string .
e.g. oopp[backspace]s return oops (delete the p)
Walkthrough:
o
oo
oop
oopp
oop [backspace]
oops
e.g. ooppp[backspace][backspace]s return oops (delete both p's)
Walkthrough:
o
oo
oop
oopp
ooppp
oopp [backspace]
oop [backspace]
oops
e.g. a[backspace][backspace]ooppp[backspace][backspace]s return oops
Walkthrough:
a
[nothing]
[nothing]
o
oo
oop
oopp
ooppp
oopp [backspace]
oop [backspace]
oops
But there's a twist! [backspace][backspace][backspace] can appear as [backspace]*3 or even [backspace]*2[backspace]
Basically, [backspace][backspace] ... [backspace] n times can appear as [backspace]*n (n can even be 1, but not less than 1 ([backspace]*0 will not occur))
e.g. a[backspace]*2oopppp[backspace]*2[backspace]s return oops
Walkthrough:
a
[nothing] [backspace]*2
o
oo
oop
oopp
ooppp
oopppp
oopp [backspace]*2
oop [backspace]
oops
To make it easier, only letters, spaces. and the [backspace] function will be in the initial string.
Good luck!
Check out the rest of the kata in this series!
Quelle: codewars.com
Lösung
Pseudo-Code
Wie immer gibt's reichlich Varianten, hier ist eine meiner.
Erst die Lösungsschritte in Pseudo-Code. Los geht’s:
Lösungsschritte
Schritt 1
Als Erstes empfehle ich dringend dem Rat des Kata-Autors zu folgen und den Vorgänger anzuschauen.
Schritt 2
Wir werden eine Variable brauchen um unser Ergebnis zu speichern, am besten ein Array.
Schritt 3
Dann können wir als Nächstes die multiplen Backspaces in einzelne auflösen. Dafür können wir uns eine kleine Helferfunktion basteln.
Schritt 4
Die einzelnen Backspaces können wir dann jeweils z.B. durch ein # ersetzen.
Schritt 5
Jetzt können wir durch den String loopen.
Schritt 6
Wenn das aktuelle Zeichen ein # ist, entfernen wir das letzte Element in unserem Ergebnis-Array.
Schritt 7
Ansonsten hängen wir das aktuelle Zeichen an unser Ergebnis an.
Schritt 8
Nach dem Loop nur noch das Ergebnis als String zurückgeben.
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Lösungsschritte
Als Erstes die Helferfunktion um die multiplen Backspaces in einzelne aufzulösen. Meine erste Zeile:
function resolveMultipleBackspaces(str: string): string {
Dann die Logik für das Ersetzen:
return str.replace(/\[backspace]\*\d+/g, (match) => {
Die RegEx /\[backspace]\*\d+/g matcht alle Zeichenfolgen mit [backspace] und * gefolgt von einer (oder mehr) Ziffer(n). Die erste eckige Klammer, das * und das d müssen wir jeweils mit einem \ escapen.
Für jeden Treffer wird eine Funktion ausgeführt, der wir das aktuelle match übergeben.
Das return können wir hier bereits davor schreiben.
Jetzt die Logik für das Innere der Replace-Funktion:
const num = Number(match.split("*")[1]);
Wir speichern uns die Zahl am Ende jedes Treffers in eine Variable.
Dann können wir so viele [backspace] zurückgeben, wie die Zahl hergibt:
return "[backspace]".repeat(num);
});
}
Und das war’s schon fürs Helferlein. Weiter geht’s mit der Hauptfunktion.
Die erste Zeile meiner Hauptfunktion (ich habe s in str umbenannt):
export function solve(str: string): string {
Dann unsere Variable für das Ergebnis:
const result: string[] = [];
Mit unserer Hilfsfunktion können wir jetzt die multiplen Backspaces (z.B. [backspace]*2) in einzelne [backspace] auflösen:
const resolvedBackspaces = resolveMultipleBackspaces(str);
[backspace]*2 wird also zu [backspace][backspace] usw.
Dann können wir alle [backspace] durch ein # ersetzen:
const backspacesReplaced = resolvedBackspaces.replace(/\[backspace]/g, "#");
Jetzt der Loop:
for (const char of backspacesReplaced) {
Da wir durch den String loopen können, empfiehlt sich hier ein einfacher for...of-Loop.
Wenn das aktuelle Zeichen ein # ist, entfernen wir das letzte Element aus unserem Ergebnis-Array:
if (char === "#") result.pop();
Ansonsten hängen wir das aktuelle Zeichen ans Ergebnis-Array an:
else result.push(char);
}
Zum Schluss nur noch das Ergebnis als String zurückgeben:
return result.join("");
}
Voilá! 💪
Zugegeben, man hätte es etwas performanter gestalten können. Dann hätte allerdings die Lesbarkeit etwas gelitten. Ich habe mich hier für die Lesbarkeit entschieden!
Komplettlösung
export function solve(str: string): string {
const result: string[] = [];
const resolvedBackspaces = resolveMultipleBackspaces(str);
const backspacesReplaced = resolvedBackspaces.replace(/\[backspace]/g, "#");
for (const char of backspacesReplaced) {
if (char === "#") result.pop();
else result.push(char);
}
return result.join("");
}
function resolveMultipleBackspaces(str: string): string {
return str.replace(/\[backspace]\*\d+/g, (match) => {
const num = Number(match.split("*")[1]);
return "[backspace]".repeat(num);
});
}