Google : 句子分割

给你一个没有间隔的字符串“thisisasentence”，如何将他分割成如下的句子：“this is a sentence”。
提供一个函数用来检验一个字符串是不是单词：bool dic(const char* beg, const char* end)；
完成下列的函数。要求效率尽可能快。
bool Detect(char* str)
{

}

尽量写出完整思路，最好有伪代码。

bool Detect(char* str)
{
  int wordBegin=0, wordEnd=0;
  char* newStr;
  while(wordBegin!=str.length()-1)
  {
    bool isWord=false;
    while(!isWord)
    {
      wordEnd++;
      isWord=dic(str.charAt(wordBegin), str.charAt(wordEnd));
      if(wordEnd==str.length()-1 && !isWord)
        return false;
    }
    newStr=newStr+str.substring(wordBegin, wordEnd)+" ";
    wordBegin=wordEnd;
  }
  str=newStr;
  return true;
}

bool Detect(char* str)
{
  int wordBegin=0, wordEnd=0;
  char* newStr;
  while(wordBegin!=str.length()-1)
  {
    bool isWord=false;
    while(!isWord)
    {
      wordEnd++;
      isWord=dic(str.charAt(wordBegin), str.charAt(wordEnd));
      if(wordEnd==str.length()-1 && !isWord)
        return false;
    }
    newStr=newStr+str.substring(wordBegin, wordEnd)+" ";
    wordBegin=wordEnd;
  }
  str=newStr;
  return true;
}
currahee 发表于 2011-5-31 21:02

贴我一个递归的版本
bool IsWord(const char* szBeg, const char* szEnd);
bool IsSplittable(const char* szString)
{
        if (*pIter == '\0') return true;

        const char* pIter = szString;
        while (*pIter != '\0')
        {
                if (IsWord(szString, pIter) && IsSplittable(pIter+1))
                        return true;
                pIter++;
        }

        return false;
}

实际问题没那么简单吧@@比如扫描到“this”之后先看到“i”也是字典里的一个单词，然后扫描发现“sasentence”不是一个单词...用回朔才能找到所有可能性吧～

回复 4# babyfrog

是有歧义的问题，比如but和button。这里必须像huffman encoding一样，限定不可以有其他词的前缀码。 当然这道题考察的肯定不会这么难。

这位同学你把char* 当做 std::string用了。。

bool Detect(char* str)
{
  int wordBegin=0, wordEnd=0;
  char* newStr;
  while(wordBegin!=str.length()-1)
  {
    bool isWord=false;
    while(!isWord)
    {
      wordEnd++;
      isWord=dic(str.charAt(wordBegin), str.charAt(wordEnd));
      if(wordEnd==str.length()-1 && !isWord)
        return false;
    }
    newStr=newStr+str.substring(wordBegin, wordEnd)+" ";
    wordBegin=wordEnd;
  }
  str=newStr;
  return true;
}
currahee 发表于 2011-5-31 21:02

回复  babyfrog

是有歧义的问题，比如but和button。这里必须像huffman encoding一样，限定不可以有其他词的前缀码。 当然这道题考察的肯定不会这么难。
stephenK 发表于 2011-7-9 15:05

    没有歧义, 这道题用递归做的话已经就算是穷举了,时间复杂度是指数的,唯一的歧义就像一个字符串可以分解成多种单词的组合,这样提供一种就够了

回复 7# wwwyhx
你的方法应该是对的，只不过那样递归复杂度太高。这题如果只要返回bool值的话，完全可以用DP，复杂度可以做到maxL*n，其中maxL是最长的单词的长度，最坏不超过n^2。

回复  wwwyhx
你的方法应该是对的，只不过那样递归复杂度太高。这题如果只要返回bool值的话，完全可以用DP，复杂度可以做到maxL*n，其中maxL是最长的单词的长度，最坏不超过n^2。
darksteel 发表于 2011-7-13 03:21

    呵呵，怎么用DP??

回复 9# wwwyhx
类似这样：

1. bool Detect(char *str)
   
2. 
   
3. {
   
4. 
   
5.     char *p, *q;
   
6. 
   
7.     bool *can = new bool[strlen(str)+1];
   
8. 
   
9.     can[0] = 1;
   
10. 
    
11.     for(p = str; *p; p++) {
    
12. 
    
13.         if(!can[p-str])
    
14. 
    
15.             continue;
    
16. 
    
17.         for(q = p; *q; q++)
    
18. 
    
19.             if(dic(p, q))
    
20. 
    
21.                 can[q-str+1] = true;
    
22. 
    
23.     }
    
24. 
    
25.     return can[strlen(str)];
    
26. 
    
27. }

复制代码

can[ i ]代表从头开始共i个字符能否被分割。内存循环其实可以到maxL也就是字典中单词的最大长度就退出，所以复杂度可以到O(maxL*n)。