Reverse Words in a String

Q: Jaka jest złożoność czasowa odwracania słów w ciągu znaków?

Oba podejścia działają w czasie O(n) dla ciągu znaków o długości n , ponieważ każdy znak jest odczytywany i zapisywany stałą liczbę razy. Podział wymaga dodatkowego miejsca O(n) na listę słów. Odwrócenie całego ciągu znaków, a następnie każdego słowa, wymaga dodatkowego miejsca O(1) w tablicy znaków, którą możesz modyfikować.

ŚrednieTablice i napisy Dwa wskaźniki

+10

Otrzymujesz ciąg znaków s złożony ze słów i spacji. Słowo to ciąg liter i cyfr, który nie zawiera spacji. Słowa mogą być oddzielone więcej niż jedną spacją, a s może zaczynać się lub kończyć spacjami.

Zwróć słowa w odwrotnej kolejności, połączone dokładnie jedną spacją, bez spacji na początku ani na końcu. Każde słowo zachowuje swoją pisownię; zmienia się tylko kolejność słów.

Funkcja

reverseWords(s: string) → string

sstring: litery, cyfry i spacje zawierające co najmniej jedno słowo
Zwracastring: słowa ciągu s w odwrotnej kolejności, oddzielone pojedynczymi spacjami

Ograniczenia

1 ≤ s.length ≤ 10⁴
s zawiera wyłącznie angielskie litery, cyfry i spacje.
s zawiera co najmniej jedno słowo.

Przykłady

Wejście: s = "Coddy runs in 15 languages"
Wyjście: "languages 15 in runs Coddy"
Wyjaśnienie: Słowa to Coddy, runs, in, 15 i languages. Czytane od ostatniego do pierwszego dają languages 15 in runs Coddy; 15 liczy się jako słowo, ponieważ słowa mogą zawierać cyfry.

Wejście: s = " practice makes progress "
Wyjście: "progress makes practice"
Wyjaśnienie: Spacje na obu końcach są usuwane, a ciągi dwóch i trzech spacji między słowami kurczą się do jednej. Trzy słowa pojawiają się od ostatniego do pierwszego: progress makes practice.

Wejście: s = " single "
Wyjście: "single"
Wyjaśnienie: Lista złożona z jednego słowa czytana od tyłu brzmi tak samo. Znikają tylko spacje wokół niego, więc odpowiedzią jest single.

Pytanie dodatkowe

Czy potrafisz odwrócić kolejność słów, zachowując odstępy w s: te same ciągi spacji, o tych samych długościach i w tej samej kolejności?

Rozwiązanie

Kolejność słów jest odwrócona; to spacje sprawiają, że rozwiązania zawodzą. Spacje na początku i na końcu oraz powtarzające się spacje między słowami muszą zniknąć, a w odpowiedzi między słowami ma być dokładnie jedna spacja. Możesz podzielić tekst na listę słów albo odwrócić cały ciąg, a następnie każde słowo w jednej tablicy.

Podziel na słowa i połącz je w odwrotnej kolejności

Intuicja

Podziel s na słowa, odwróć listę i połącz ją pojedynczymi spacjami. Dzielenie wymaga uwagi: podział " practice makes progress " przy każdej pojedynczej spacji daje sześć pustych elementów wokół trzech słów. Usuń puste elementy, a lista będzie zawierać practice, makes, progress.

Dzielenie odczytuje każdy znak raz, a łączenie zapisuje każdy zachowany znak raz, więc czas działania wynosi O(n) dla ciągu o długości n. Lista słów i wynik wymagają dodatkowej przestrzeni O(n).

Algorytm

Podziel s według spacji.
Usuń puste elementy.
Odwróć listę słów.
Połącz słowa, wstawiając jedną spację między każde z nich, i zwróć wynik.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

Odwróć cały ciąg znaków, a następnie każde słowo

Intuicja

Odwrócenie całego ciągu znaków umieszcza słowa we właściwej kolejności, ale zapisuje każde z nich wspak: Coddy runs in 15 languages zmienia się w segaugnal 51 ni snur yddoC. Następnie odwrócenie każdego słowa osobno daje languages 15 in runs Coddy.

Spacje są obsługiwane w tym samym przebiegu. Indeks read przechodzi po odwróconej tablicy i pomija spacje; indeks write wskazuje miejsce, w którym ma się znaleźć następny zachowany znak. Kopiowanie nigdy nie nadpisuje znaku, który jest jeszcze potrzebny, ponieważ write nigdy nie wyprzedza read: pojedyncza spacja zapisana przed słowem zastępuje co najmniej jedną spację pominiętą przez read.

Każdy znak jest kopiowany co najwyżej raz i zamieniany miejscami co najwyżej dwa razy, więc złożoność czasowa wynosi O(n), a dodatkowa przestrzeń wynosi O(1) w przypadku edytowalnego bufora znaków. Ciągi znaków są tu przekazywane jako wartości, więc każde rozwiązanie tworzy jedną roboczą kopię s: łącznie O(n) pamięci.

Algorytm

Skopiuj s do tablicy znaków i odwróć całą tablicę.
Przejdź po tablicy, używając indeksu odczytu, i pomijaj spacje.
Dla każdego słowa najpierw zapisz jedną spację, chyba że jest to pierwsze słowo, a następnie skopiuj znaki słowa pod indeks zapisu.
Odwróć skopiowany fragment, aby słowo było zapisane od przodu.
Zwróć pierwsze write znaków.

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

Pułapki i przypadki brzegowe

Dzielenie po pojedynczej spacji i zachowywanie każdego fragmentu. "a b" dzieli się na a, pusty fragment i b, a łączenie przywraca dwie spacje: "b a".
Zakładanie, że dzielenie usuwa puste fragmenty z obu końców. Metoda Java split(" ") usuwa puste fragmenty z końca, ale zachowuje je na początku, więc " a b" nadal pozostawia jeden.
Dodawanie spacji po każdym słowie, również po ostatnim, przez co odpowiedź kończy się spacją. Wstaw spację przed każdym słowem oprócz pierwszego.
Wykonanie tylko jednego odwrócenia w wersji działającej w miejscu. Odwrócenie samych słów daje yddoC snur ni 51 segaugnal.
W PHP i R dane wejściowe składające się wyłącznie z cyfr, takie jak 2026, mogą zostać przekazane jako liczba. Przed podziałem zamień je na ciąg znaków.

Najczęstsze pytania3

Jaka jest złożoność czasowa odwracania słów w ciągu znaków?

Oba podejścia działają w czasie O(n) dla ciągu znaków o długości n, ponieważ każdy znak jest odczytywany i zapisywany stałą liczbę razy. Podział wymaga dodatkowego miejsca O(n) na listę słów. Odwrócenie całego ciągu znaków, a następnie każdego słowa, wymaga dodatkowego miejsca O(1) w tablicy znaków, którą możesz modyfikować.

Jak obsługiwać wiele spacji między wyrazami?

Traktuj słowo jako ciąg znaków innych niż spacje i nigdy nie kopiuj spacji z danych wejściowych. Podział bez separatora w Pythonie i Ruby, strings.Fields w Go oraz split_whitespace w Rust już pomija każdy ciąg spacji i oba jego końce; w pozostałych przypadkach usuń puste elementy. Następnie wstaw jedną spację między słowami.

Czy potrafisz odwrócić kolejność słów bez użycia funkcji split?

Tak. Skanuj od prawego końca: pomijaj spacje, zaznaczaj miejsce, w którym kończy się słowo, przesuwaj się w lewo do jego początku i dodawaj słowo, poprzedzając je spacją, chyba że jest pierwsze. Każdy znak jest odwiedzany raz, więc czas działania pozostaje równy O(n), a słowa pojawiają się w odwrotnej kolejności bez konieczności odwracania listy.

def reverseWords(s):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

s = "Coddy runs in 15 languages"

Oczekiwany wynik

"languages 15 in runs Coddy"