一个关于算法的面试题。
在网上突然看到这么个东东。想了半天。没头绪。。。。。内容如下：
给你一个没有间隔的字符串“thisisasentence”，如何将他分割成如下的句子：“this is a sentence”。
提供一个函数用来检验一个字符串是不是单词：bool dic(char* w)；完成下列的函数。要求效率尽可能快。
bool Detect(char* str)
{
}
尽量写出完整思路，最好有伪代码。
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
这个问题应该还是回归到分词上，用中文分词的方法来分析英文字母
这个应该得有个词库来对比吧，不然你怎么知道几个字母是一个词汇呢
或者干脆你用隐马尔科夫模型来统计判断几个字母是一个单词的概率
这个是分词嘛
看起来像是英文分词，但实际做法倒类似于中文分词
可以去搜索这方面的论文
都发表发表看法么，
这个，我觉得只提供一个bool dic（char* w）函数是不够的，比如我判断"thi"是不是单词之后又要重新判断"this"是不是单词，这里面必然有重复的工作。我想在dic函数里面，一定有一个字典库，它是按字母分类存储的多层的多叉树结构，每判断一次不论true/false，应该同时返回"thi"在字典中的位置（指针、地址，单词加上词组和常用句子的个数不过几十万，可以用线性寻址，而不必记录从树根到树节点的路径），下一次判断"this"的时候同时传进去上一次的位置（指针、地址）。开始找一个新的单词时，要返回树根地址。
当然这只是第一步，重点是找单词的策略。像如下的单词是很难找的"bookstore"、"biggest"等，前面一部分是单词，后面也是单词，前面是单词，后面不是单词，因此，即使dic返回true也不能直接认为要加一个“空格”。要往后找，直到找到一个最长的单词吗？多长算最长呢？不好说。这还是需要在字典库中做文章，即每个单词要有一个属性，就是它是不是某个单词的前缀，dic函数同样要返回这个属性。
在一个句子中，把两个单词连成一个最长的单词，有时候还不一定是最好的，这跟语义相关，就麻烦了！字典中还要有各种词法、句法，相当麻烦。
如果不考虑语义，我想前两段应该还不够，可能出现这种情况，str1str2str3中，str1是一个单词，str1str2也是一个单词，str2str3是另外一个单词，但是str2和str3都不是单独的单词。这就麻烦了，你一味地找最长的单词，结果str3成立孤家寡人！我也没有什么好的办法。难道同时把str1和str1str2都认为是单词，形成两个独立的分支分别找下去？如果这样的分支很多呢？
没有伪代码，抱歉！