拼音分割的思路请教

Question

请教一个题目：



测试题目

拼音：zhongguorenminzhanqilaile

分割目标：zhong guo ren min zhan qi lai le

要求不使用第三方工具，自己给出合理算法。



可以告诉一下实现思路么？可以暂时不考虑特殊情况，比如xian之类



谢谢。。。

Answer 1

排好序的拼音表用二分查找的话效率也还可以接受吧？

简单的实现方法就是把一个字所有可能的拼音都预先放在一个表（Java的话也就是数组了）里，注意按字母顺序排好序。由于汉语拼音可能出现前缀重叠的现象（e.g. zhe/zhen/zheng），不考虑特殊情况的话这里应该使用贪婪算法。把字符串从左向右扫描，当发现匹配时继续扫描，直到又变得不匹配或者遇到结尾为止。
例如说，
guoren
从0位置开始，不断取substring来对拼音表做匹配
0-0 g 没有匹配
0-1 gu 有匹配，继续
0-2 guo 有匹配，继续
0-3 guor 没有匹配，记录下guo，并将下一轮扫描的起始位置设到3
3-3 r 没有匹配
3-4 re 有匹配，继续
3-5 ren 有匹配，继续
3-eof ren 遇到结尾，记录下ren，结束。
如果输入的拼音有错误，那么同样在遇到字符串结尾的时候结束；遇到结尾时可以观察上一轮扫描是否有匹配，有匹配的时候记录，没有的话说明输入的拼音有错误，可以适当做些错误处理。