如何将字符串拆分为单词.例如:“stringintowords"->“串成词"? [英] How to split a string into words. Ex: "stringintowords" -> "String Into Words"?

问题描述

将字符串拆分为单词的正确方法是什么?(字符串不包含任何空格或标点符号)

What is the right way to split a string into words ? (string doesn't contain any spaces or punctuation marks)

例如:"stringintowords" -> "String Into Words"

For example: "stringintowords" -> "String Into Words"

你能建议这里应该使用什么算法吗?

Could you please advise what algorithm should be used here ?

！更新:对于那些认为这个问题只是出于好奇的人.该算法可用于将域名(sportandfishing .com" -> SportAndFishing .com")转换为驼峰格式，aboutus dot org 目前使用此算法来动态进行此转换.

! Update: For those who think this question is just for curiosity. This algorithm could be used to camеlcase domain names ("sportandfishing .com" -> "SportAndFishing .com") and this algo is currently used by aboutus dot org to do this conversion dynamically.

推荐答案

正如这里很多人所提到的，这是一个标准的、简单的动态规划问题:Falk Hüffner 给出了最佳解决方案.附加信息:

As mentioned by many people here, this is a standard, easy dynamic programming problem: the best solution is given by Falk Hüffner. Additional info though:

(a) 您应该考虑使用 Trie 来实现 isWord，如果您使用得当(即通过逐步测试单词)，这将为您节省大量时间.

(a) you should consider implementing isWord with a trie, which will save you a lot of time if you use properly (that is by incrementally testing for words).

(b) 输入segmentation dynamic programming"会得到分数更详细的答案，来自使用伪代码算法的大学级讲座，例如 杜克大学的这个讲座(甚至提供了一种简单的概率方法来处理当你有单词赢了时该怎么办'不包含在任何字典中).

(b) typing "segmentation dynamic programming" yields a score of more detail answers, from university level lectures with pseudo-code algorithm, such as this lecture at Duke's (which even goes so far as to provide a simple probabilistic approach to deal with what to do when you have words that won't be contained in any dictionary).

这篇关于如何将字符串拆分为单词.例如:“stringintowords"->“串成词"?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！