Schwierig 2 gelöst 66.7% Erfolgsquote

Word Break

Decide whether text can be split into dictionary words.

Das lernst du

  • Markieren, welche Präfixe zerlegbar sind
  • Eine Menge für schnelle Wörterbuchabfragen nutzen
  • Eine boolesche DP über Positionen aufbauen

Problem

Decide whether text can be split into a sequence of words from words. Words may be reused. Dynamic programming over prefixes solves it efficiently.

Implement can_break(text, words).

Input

text: Lowercase letters only. words: The dictionary; each word has 1–50 lowercase letters.

Output

Return true if a split exists.

Einschränkungen

0 ≤ length of text ≤ 5,000; 1 ≤ words ≤ 1,000

Beispiele

Beispiel 1
Eingabe:
text = "applepenapple"
words = ["apple", "pen"]

Erwartete Ausgabe:
expected = True
Eingabe:
std::string text = "applepenapple";
std::vector<std::string> words = {"apple", "pen"};

Erwartete Ausgabe:
bool expected = true;
Eingabe:
string text = "applepenapple";
string[] words = new string[] {"apple", "pen"};

Erwartete Ausgabe:
bool expected = true;

Erläuterung

"apple" + "pen" + "apple", reusing "apple".

Beispiel 2
Eingabe:
text = "catsandog"
words = ["cats", "dog", "sand", "and", "cat"]

Erwartete Ausgabe:
expected = False
Eingabe:
std::string text = "catsandog";
std::vector<std::string> words = {"cats", "dog", "sand", "and", "cat"};

Erwartete Ausgabe:
bool expected = false;
Eingabe:
string text = "catsandog";
string[] words = new string[] {"cats", "dog", "sand", "and", "cat"};

Erwartete Ausgabe:
bool expected = false;

Erläuterung

Every split leaves "og" or "ando" unmatched: false.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Ein Präfix ist zerlegbar, wenn eine frühere zerlegbare Position es mit einem Wörterbuchwort erreicht.

Hinweis 2

Dynamische Programmierung über Positionen funktioniert gut, wenn du Wortlängen oder Wörterbucheinträge effizient prüfst.

Hinweis 3

Leerer Text ist trivial zerlegbar, aber die wiederholte Verwendung von Wörtern sollte während des gesamten Durchlaufs erlaubt bleiben.

Erwartete Komplexität

Zeit O(n^2), zusätzlicher Speicher O(n)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 806 ms - 5/5 Code ansehen
2 KKKaneki Ken Python 851 ms - 2/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 2 vollständige Lösungen unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.