Блог пользователя nhtrnm

Разбить строку на слова из словаря
Автор nhtrnm, 10 лет назад, перевод, По-русски

Хочу найти такую задачу:
Дана строка s массив слов a, разбейте s на слова a так, что как можно меньше символов не принадлежали никаким словам.
Если s = 'aabbac' и a = {'aabb', 'c', 'aab', 'bac'} я ожидаю, что s будет разбит как , а не как так как в последнем случае есть лишний символ.
Я уверен, что где-то в сети есть такая задача, может ли кто-нибудь дать мне на нее ссылку?
Спасибо.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Лучше скажи, за сколько ты умеешь ее решать.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Знатоки баянов, где вы? Аууу! Отзовитесь!

Нет, ну серьезно. Я не вижу в решении за ни одной новой идеи. Такие задачи обязательно должны где-то разбираться.

Идея решения в первой правке.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

    spoiler

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Извиняюсь за неправильную постановку акцента в комментарии.

      Здесь еще один спойлер.

      Спрячь и ты свой комментарий, пожалуйста.

      → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А их точно не более?

    Например, слова

    "a";"ab";"abc"

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      Это приблизительная оценка. Если более точно — пусть у нас k строк с возрастающей длиной. Их суммарная длина будет не меньше . Отсюда легко можно вычислить оценку сверху на k через n:

      → Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    UPD: Прочитал правку следующего комментария, теперь все нормально. Но все же, не очень удобный способ общаться правками.

    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

Спасибо всем знатокам, ваша помощь оказалась для автора бесценной. Я уж не знаю, какими цензурными словами критиковать зеленого участника, создавшего этот пост.

P.S. На случай внезапного удаления поста: его автор спрашивает о задаче SPOJ MORSE.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Оно?

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here is the link

Medium https://oj.leetcode.com/problems/word-break/

Hard https://oj.leetcode.com/problems/word-break-ii/

Hope this may help you ...

→ Ответить