Рубрики

Проблема с разрывом слов | DP-32

По заданной входной строке и словарю слов выясните, можно ли разделить входную строку на разделенную пробелами последовательность слов словаря. Смотрите следующие примеры для более подробной информации.
Это известный вопрос об интервью в Google, который также задают многие другие компании уже несколько дней.

Consider the following dictionary 
{ i, like, sam, sung, samsung, mobile, ice, 
  cream, icecream, man, go, mango}

Input:  ilike
Output: Yes 
The string can be segmented as "i like".

Input:  ilikesamsung
Output: Yes
The string can be segmented as "i like samsung" 
or "i like sam sung".

Рекурсивная реализация:
Идея проста, мы рассматриваем каждый префикс и ищем его в словаре. Если префикс присутствует в словаре, мы повторяем для остальной части строки (или суффикса). Если рекурсивный вызов для суффикса г

def wordBreak(wordList, word):

    if word == '':

        return True

    else:

        wordLen = len(word)

        return any([(word[:i] in wordList) and wordBreak(wordList, word[i:]) for i in range(1, wordLen+1)])

eturns true, мы возвращаем true, в противном случае мы пытаемся использовать следующий префикс. Если мы перепробовали все префиксы и ни один из них не привел к решению, мы возвращаем false.

Мы настоятельно рекомендуем видеть функцию substr, которая широко используется в следующих реализациях.

C ++

// Рекурсивная программа для проверки, является ли данный
// строка может быть сегментирована на пробел
// слова в словаре
#include <iostream>

using namespace std;

  
/ * Утилита для проверки, является ли слово

  присутствует в словаре или нет. Массив строк

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

  словарь определенно не очень хорошая идея. У нас есть

  используется для простоты программы * /

int dictionaryContains(string word)

{

    string dictionary[] = {"mobile","samsung","sam","sung",

                            "man","mango","icecream","and",

                             "go","i","like","ice","cream"};

    int size = sizeof(dictionary)/sizeof(dictionary[0]);

    for (int i = 0; i < size; i++)

        if (dictionary[i].compare(word) == 0)

           return true;

    return false;

}

  
// возвращает true, если строка может быть сегментирована в пространство
// разделенные слова, в противном случае возвращает false

bool wordBreak(string str)

{

    int size = str.size();

  

    // Базовый вариант

    if (size == 0)  return true;

  

    // Попробуйте все префиксы длины от 1 до размера

    for (int i=1; i<=size; i++)

    {

        // Параметр для dictionaryContains - это

        // str.substr (0, i), который является префиксом (ввода

        // строка) длины 'i'. Сначала мы проверим,

        // текущий префикс в словаре. Тогда мы

        // рекурсивно проверяем оставшуюся строку

        // str.substr (i, size-i), который является суффиксом

        // длина size-i

        if (dictionaryContains( str.substr(0, i) ) &&

            wordBreak( str.substr(i, size-i) ))

            return true;

    }

  

    // Если мы перепробовали все префиксы и

    // никто из них не работал

    return false;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    wordBreak("ilikesamsung")? cout <<"Yes\n": cout << "No\n";

    wordBreak("iiiiiiii")? cout <<"Yes\n": cout << "No\n";

    wordBreak("")? cout <<"Yes\n": cout << "No\n";

    wordBreak("ilikelikeimangoiii")? cout <<"Yes\n": cout << "No\n";

    wordBreak("samsungandmango")? cout <<"Yes\n": cout << "No\n";

    wordBreak("samsungandmangok")? cout <<"Yes\n": cout << "No\n";

    return 0;

}

Джава

import java.util.*;

  
// Рекурсивная реализация
// проблема с разрывом слов в Java

public class WordBreakProblem

{

  

    // установить для хранения словарных значений

    private static Set<String> dictionary = new HashSet<>();

      

    public static void main(String []args)

    {

          

        // массив строк для добавления в словарный набор.

        String temp_dictionary[] = {"mobile","samsung","sam","sung"

                            "man","mango","icecream","and"

                            "go","i","like","ice","cream"};

                              

        // цикл для добавления всех строк в словарь

        for (String temp :temp_dictionary)

        {

            dictionary.add(temp);

        }

          

        // примеры входных данных

        System.out.println(wordBreak("ilikesamsung"));

        System.out.println(wordBreak("iiiiiiii"));

        System.out.println(wordBreak(""));

        System.out.println(wordBreak("ilikelikeimangoiii"));

        System.out.println(wordBreak("samsungandmango"));

        System.out.println(wordBreak("samsungandmangok"));

          

    }

      

    // возвращает true, если слово может быть разбито на части

    // каждая часть содержится в словаре

    public static boolean wordBreak(String word)

    {

        int size = word.length();

          

        // базовый вариант

        if (size == 0)

        return true;

          

        // еще проверить все слова

        for (int i = 1; i <= size; i++)

        {

            // Теперь мы сначала разделим слово на две части,

            // префикс будет иметь длину i и проверять, если это

            // присутствует в словаре, если да, то мы проверим

            // суффикс длины size-i рекурсивно. если оба префикса и

            // суффикс присутствует, слово найдено в словаре.

  

            if (dictionary.contains(word.substring(0,i)) && 

                    wordBreak(word.substring(i,size)))

            return true;

        }

          

        // если все случаи были неудачными, вернуть false

        return false;

    }

}

  
// Этот код предоставлен Sparsh Singhal

Выход:

Yes
Yes
Yes
Yes
Yes
No

Динамическое программирование
Почему динамическое программирование? Вышеуказанная проблема имеет перекрывающиеся подзадачи. Например, см. Следующее дерево частичной рекурсии для строки «abcde» в худшем случае.

// Программа на основе динамического программирования для проверки, может ли данная строка
// быть разделенным на слова в словаре
#include <iostream>
#include <string.h>

using namespace std;

  
/ * Утилита для проверки наличия слова в словаре или нет.

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

  словарь определенно не очень хорошая идея. Мы использовали для простоты

  программа*/

int dictionaryContains(string word)

{

    string dictionary[] = {"mobile","samsung","sam","sung","man","mango",

                           "icecream","and","go","i","like","ice","cream"};

    int size = sizeof(dictionary)/sizeof(dictionary[0]);

    for (int i = 0; i < size; i++)

        if (dictionary[i].compare(word) == 0)

           return true;

    return false;

}

  
// Возвращает true, если строка может быть сегментирована на пробел
// слова, в противном случае возвращает false

bool wordBreak(string str)

{

    int size = str.size();

    if (size == 0)   return true;

  

    // Создаем таблицу DP для хранения результатов подзадач. Значение wb [i]

    // будет истинным, если str [0..i-1] можно сегментировать в словарные слова,

    // иначе ложно.

    bool wb[size+1];

    memset(wb, 0, sizeof(wb)); // Инициализировать все значения как ложные.

  

    for (int i=1; i<=size; i++)

    {

        // если wb [i] имеет значение false, тогда проверить, может ли текущий префикс сделать его истинным.

        // Текущий префикс "str.substr (0, i)"

        if (wb[i] == false && dictionaryContains( str.substr(0, i) ))

            wb[i] = true;

  

        // wb [i] равно true, затем проверяем все подстроки, начиная с

        // (i + 1) -й символ и сохраняем их результаты.

        if (wb[i] == true)

        {

            // Если мы достигли последнего префикса

            if (i == size)

                return true;

  

            for (int j = i+1; j <= size; j++)

            {

                // Обновление wb [j], если оно ложно и может быть обновлено

                // Обратите внимание, что параметр, переданный в dictionaryContains ()

                // подстрока, начинающаяся с индекса 'i' и длины 'ji'

                if (wb[j] == false && dictionaryContains( str.substr(i, j-i) ))

                    wb[j] = true;

  

                // Если мы достигли последнего символа

                if (j == size && wb[j] == true)

                    return true;

            }

        }

    }

  

    / * Раскомментируйте эти строки для печати таблицы DP "wb []"

     для (int i = 1; i <= size; i ++)

        cout << "" << wb [i]; * /

  

    // Если мы испробовали все префиксы и ни один из них не сработал

    return false;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    wordBreak("ilikesamsung")? cout <<"Yes\n": cout << "No\n";

    wordBreak("iiiiiiii")? cout <<"Yes\n": cout << "No\n";

    wordBreak("")? cout <<"Yes\n": cout << "No\n";

    wordBreak("ilikelikeimangoiii")? cout <<"Yes\n": cout << "No\n";

    wordBreak("samsungandmango")? cout <<"Yes\n": cout << "No\n";

    wordBreak("samsungandmangok")? cout <<"Yes\n": cout << "No\n";

    return 0;

}

Выход:

Yes
Yes
Yes
Yes
Yes
No

Оптимизированное динамическое программирование :
В этом подходе, кроме таблицы dp, мы также поддерживаем все индексы, которые соответствовали ранее. Затем мы проверим подстроки из этих индексов в текущий индекс. Если кто-нибудь из этого совпадает, мы можем разделить строку до этого индекса.

В этой программе мы используем дополнительное пространство. Однако его временная сложность составляет O (n * s), где s — длина самой большой строки в словаре, а n — длина данной строки.

// Программа для динамического программирования для тестирования
// может ли данная строка быть сегментирована на
// разделенные пробелом слова в словаре
#include <bits/stdc++.h>

using namespace std;

  
/ * Полезная функция, чтобы проверить, является ли слово

   присутствует в словаре или нет. Массив

   Строки используются для словаря. Используя массив

   строк для словаря определенно нет

   хорошая идея. Мы использовали для простоты

   программа*/

int dictionaryContains(string word)

{

    string dictionary[] = { "mobile", "samsung", "sam",

                            "sung", "man", "mango",

                            "icecream", "and", "go",

                            "i", "like", "ice", "cream" };

    int size = sizeof(dictionary) / sizeof(dictionary[0]);

    for (int i = 0; i < size; i++)

        if (dictionary[i].compare(word) == 0)

            return true;

    return false;

}

  
// Возвращает true, если строка может быть сегментирована в пространство
// разделенные слова, в противном случае возвращает false

bool wordBreak(string s)

{

    int n = s.size();

    if (n == 0)

        return true;

  

    // Создаем таблицу DP для хранения результатов подзадач.

    // Значение dp [i] будет истинным, если str [0..i] может быть

    // сегментируется на словарные слова, иначе ложь

    vector<bool> dp(n + 1, 0); // Инициализируем все значения

    // как ложь.

  

    // массив matched_index представляет индексы, для которых

    // dp [i] - это правда. Изначально присутствует только -1 элемент

    // в этом массиве.

    vector<int> matched_index;

    matched_index.push_back(-1);

  

    for (int i = 0; i < n; i++) {

        int msize = matched_index.size();

  

        // Значение флага, которое сообщает, что подстрока соответствует

        // с заданными словами или нет.

        int f = 0;

  

        // Проверяем всю подстроку из найденных индексов

        // ранее. Если какая-либо из этой подстроки соответствует чем

        // make flag value = 1;

        for (int j = msize - 1; j >= 0; j--) {

  

            // sb это подстрока, начинающаяся с matched_index [j]

            // + 1 и длины i - matched_index [j]

            string sb = s.substr(matched_index[j] + 1, i - matched_index[j]);

  

            if (dictionaryContains(sb)) {

                f = 1;

                break;

            }

        }

  

        // Если подстрока соответствует, чем сделать dp [i] = 1 и

        // вставить этот индекс в массив matched_index.

        if (f == 1) {

            dp[i] = 1;

            matched_index.push_back(i);

        }

    }

    return dp[n - 1];

}

  
// Код драйвера

int main()

{

    wordBreak("ilikesamsung") ? cout << "Yes\n" : cout << "No\n";

    wordBreak("iiiiiiii") ? cout << "Yes\n" : cout << "No\n";

    wordBreak("") ? cout << "Yes\n" : cout << "No\n";

    wordBreak("ilikelikeimangoiii") ? cout << "Yes\n" : cout << "No\n";

    wordBreak("samsungandmango") ? cout << "Yes\n" : cout << "No\n";

    wordBreak("samsungandmangok") ? cout << "Yes\n" : cout << "No\n";

    return 0;

}

Выход:

Yes
Yes
Yes
Yes
Yes
No

Проблема с разрывом слов | (Три решение)

Упражнение:
Вышеуказанные решения только выясняют, может ли данная строка быть сегментирована или нет. Расширьте вышеупомянутое решение динамического программирования для печати всех возможных разделов входной строки.

Примеры:

Input: ilikeicecreamandmango
Output: 
i like ice cream and man go
i like ice cream and mango
i like icecream and man go
i like icecream and mango

Input: ilikesamsungmobile
Output:
i like sam sung mobile
i like samsung mobile

Обратитесь к сообщению ниже для решения упражнений.
Проблема с разрывом слов при использовании Backtracking

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проблема с разрывом слов | DP-32

0.00 (0%) 0 votes