C - The Cow Lexicon POJ - 3267

╰半橙微兮° 2022-02-21 03:27 143阅读 0赞

### 题目描述： ###

Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters ‘a’…‘z’. Their cowmunication system, based on mooing, is not very accurate; sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said “browndcodw”. As it turns out, the intended message was “browncow” and the two letter "d"s were noise from other parts of the barnyard.

The cows want you to help them decipher a received message (also containing only characters in the range ‘a’…‘z’) of length L (2 ≤ L ≤ 300) characters that is a bit garbled. In particular, they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.

Input  
Line 1: Two space-separated integers, respectively: W and L  
Line 2: L characters (followed by a newline, of course): the received message  
Lines 3… W+2: The cows’ dictionary, one word per line  
Output  
Line 1: a single integer that is the smallest number of characters that need to be removed to make the message a sequence of dictionary words.  
Sample Input  
6 10  
browndcodw  
cow  
milk  
white  
black  
brown  
farmer  
Sample Output  
2  
题意： 给你一个长度为L的字符串。问你最少删除多少个字符，使得这个字符串里面的字母，都是给出单词表中的单词。  
分析：  
本题数据范围比较小。 但是我也不会做，还是看了题解。  
首先，要保证字符里面每个单词都是给定的单词表中的内容。 那么我们可以从后面往前面依次遍历。  
简单分析：  
第一次， 是字符串中的最后一个字母。我们，以这个字母为起点看字符串中有没有匹配的单词。 如果有那么就可以考虑更新dp值。 一直这样下去，直到第一个子母。  
那么我们需要建立一个一维dp就好了。  
参考博客：[https://blog.csdn.net/qq\_39384461/article/details/81277733][https_blog.csdn.net_qq_39384461_article_details_81277733]  
代码：

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    char str[610][310];
    char s[610];
    int dp[610];
    int main()
    {
        int W,L;
        scanf("%d%d",&W,&L);
            scanf("%s",s);
            for(int i=0; i<W; i++)
                {
                    scanf("%s",str[i]);
                }
            dp[L]=0;
            for(int i=L-1; i>=0; i--)
            {
                dp[i]=dp[i+1]+1;//先假设这个字母会被删除
              //  printf("%c",s[i]);
                for(int j=0; j<W; j++)//循环遍历单词表
                {
                    int len=strlen(str[j]);
                    if(L-i>=len&&str[j][0]==s[i])
                    //如果待匹配的字符串长度比当前单词长度大，并且首子母相同就进一步判断
                    {
                        int p1=i;
                        int p2=0;
                        while(p1<L)
                        {
                            if(s[p1]==str[j][p2])
                            {
                              //  printf("%c",s[p1]);
                                p1++;
                                p2++;
                            }
                            else
                                p1++;
                            if(p2==len)//表示能匹配成功，更新dp值
                            {
                              //  printf("\n%s\n",str[j]);
                                dp[i]=min(dp[i],dp[p1]+p1-i-len);
                                break;
                            }
                        }
                        //printf("\n");
                    }
                }
            }
            printf("%d\n",dp[0]);
            return 0;
    }

[https_blog.csdn.net_qq_39384461_article_details_81277733]: https://blog.csdn.net/qq_39384461/article/details/81277733