ps断字_断字问题

分手后的思念是犯贱 2023-03-05 09:36 13阅读 0赞

ps断字

**Problem Statement:**

**问题陈述：**

Given a dictionary, you have to split a given string into meaningful words.

给定字典，您必须将给定的字符串拆分为有意义的单词。

**Example:**

**例：**

Case-I:
        If the dictionary contain the words: 
        {"like", "i" , "ice" , "cream", "is"};
        Input : "ilikeicecream"
        Output: "i like ice cream"
    
        Case-II:
        If the dictionary contain the words: 
        {"like", "i" , "ice" , "cream", "is"}
        Input: "ilikeeicecream"
        Output: False 
        (There is no combination possibleout from the dictionary)

**Algorithm:**

**算法：**

We solve the problem using dynamic programming. The problem contains two parts one is detecting the words and the other one is retrieving the words.

我们使用动态编程解决了这个问题。 该问题包括两部分：一个是检测单词，另一个是检索单词。

**Case-I**

**案例一**

1.  We take a Boolean array of length the same as the length of the string and initialize it with false.
    
    我们采用长度与字符串长度相同的布尔数组，并使用false对其进行初始化。
2.  We take a vector and initialize it with -1.
    
    我们取一个向量并将其初始化为-1。
3.  We start comparing the string from position 0 and increment the length at each time by one.
    
    我们从位置0开始比较字符串，并将每次的长度加一。
4.  Whenever we find a meaningful word we push\_back() that index into the vector and make that index in the boolean array true.
    
    每当我们找到有意义的词时，我们都将push\_back()索引到向量中，并使布尔数组中的该索引为true。
5.  After inserting the index then we start checking the next word from that index and also the previous index.
    
    插入索引后，我们开始检查该索引中的下一个单词以及上一个索引。
6.  Repeat step 2 to step 5 until we traverse the whole string.
    
    重复步骤2到步骤5，直到遍历整个字符串。
7.  If the (length -1) index in the boolean array is true then we separate the string otherwise we don't.
    
    如果布尔数组中的(length -1)索引为true，则我们将字符串分开，否则不这样做。

**Case-II**

**案例二**

1.  We take the sub-string from the last element of the vector to the last of the string and check to the dictionary.
    
    我们从向量的最后一个元素到字符串的最后一个子字符串，然后检查字典。
2.  If found then next time last will be the last element of the vector.
    
    如果找到，则下一次last将是向量的最后一个元素。
3.  If not found then only go to the next to last element of that vector.
    
    如果找不到，则仅转到该向量的倒数第二个元素。
4.  Repeat the process until we go to the first element of the vector.
    
    重复该过程，直到转到向量的第一个元素。

## 分词问题的C ++实现 **(**C++ Implementation for word break problem**)** ##

#include <bits/stdc++.h>
    using namespace std;
    
    bool dictionary_contain(string str, string* dictionary, int num)
    {
        
        for (int i = 0; i < num; i++) {
        
            //if any word match with the word
            //in the dictionary then break the loop
            if (dictionary[i].compare(str) == 0)
                return true;
        }
        return false;
    }
    
    bool word_split(string s, vector<int>& ind, string* dictionary, int num)
    {
        
        int len = s.size();
        //if the string is empty then it true
        if (len == 0)
            return true;
        //decleare the boolean array of length
        //same as the string
        vector<int> dp(len, 0);
        ind.push_back(-1);
        for (int i = 0; i < len; i++) {
        
            int size = ind.size();
            int tag = 0;
            for (int j = size - 1; j >= 0; j--) {
        
                string sb = s.substr(ind[j] + 1, i - ind[j]);
                if (dictionary_contain(sb, dictionary, num)) {
        
                    tag = 1;
                    break;
                }
            }
            if (tag) {
        
                dp[i] = 1;
                ind.push_back(i);
            }
        }
        return dp[len - 1];
    }
    
    int main()
    {
        
        string s = "ilikeicecream";
        //contains of the dictionary
        string dictionary[] = {
         "i", "like", "ice", "cream", "is", "cool" };
        int num = sizeof(dictionary) / sizeof(dictionary[0]);
        vector<int> ind;
        if (word_split(s, ind, dictionary, num)) {
        
            cout << "True" << endl;
            vector<int>::iterator it;
            string str = "";
            int last = s.size();
            int len = 0;
            int* arr = new int[ind.size()];
            for (it = ind.begin(); it != ind.end(); it++) {
        
                arr[len++] = *it;
            }
            list<string> word;
            for (int i = len - 1; i >= 0; i--) {
        
                str = s.substr(arr[i] + 1, last - arr[i]);
                if (dictionary_contain(str, dictionary, num)) {
        
                    last = arr[i];
                    word.push_front(str);
                    str = "";
                }
            }
            list<string>::iterator i;
            for (i = word.begin(); i != word.end(); i++) {
        
                cout << *i << " ";
            }
        }
        else {
        
            cout << "false" << endl;
        }
        return 0;
    }

**Output**

**输出量**

True
    i like ice cream

> 翻译自: [https://www.includehelp.com/icp/word-break-problem.aspx][https_www.includehelp.com_icp_word-break-problem.aspx]

ps断字

[https_www.includehelp.com_icp_word-break-problem.aspx]: https://www.includehelp.com/icp/word-break-problem.aspx