DataStructuresAndAlgorithm--字谜游戏
参考:http://tieba.baidu.com/p/2071585293
输入是由一些字母构成的一个二维数组以及一些单词组成。目标是要找出字谜中的单词,这些单词可能是水平、垂直或沿对角线上任何方向放置的。
作为例子,如下所示的字谜由单词 this 从第一行第一列的位置即(1,1)处开始并延伸至(1,4);单词 two 从(1,1)到(3,1);fat 从(4,1)到(2,3);而 that 则从(4,4) 到(1,1)。
现在至少有两种直观的算法来求解这个问题。对单词表中的每个单词,我们检查每一个有序三元组(行、列、方向)验证是否有单词存在。这需要大量嵌套的 for 循环,但他基本上是直观的算法。
也可以这样,对于每一个尚未月初谜板边缘的有序四元组(行、列、方向、字符数)我们可以测试是否所指的单词在单词表中。这也导致使用大量嵌套的 for 循环。如果在任意单词的最大字符数已知,那么该算法可能节省一些时间。
那么,如何判断一个字符串是否为一个单词。
第一个思路最简单,识别出个六级英语单词表,然后稍加整理做成数据库。
然后程序就通过查表来识别单词。
·第二个思路稍微复杂点,按照你的要求,识别率肯定超过100%,不过就是可能会出现一些不存在的词。
一般英文单词的构成都是前缀 + 本体 + 后缀。
而且排列都是辅音后加元音。
按照这种排列去识别英文单词。
·第三个思路是利用各大网站的查询系统,识别率可以达到99.99%,不过要求联网,会一些HTTP知识以及网络编程:
我举的例子用百度词典来做查询引擎(不过因为百度的识别率太高,会出现一些很奇特的问题,你可以试试用其他引擎,金山词霸,或者Google翻译。)。
具体步骤如下:
连接到http://dict.baidu.com/s?wd=%s&f=3&dt=explain
其中%s替换成我们的英文单词。
然后,检查返回的内容。
如果发现“词典中没有与您搜索的关键词匹配的内容”这个字符串,那么就说明这个单词不存在,否则就是存在的。
最新文章
- c++ 奇特的递归模板模式(CRTP)
- 微软云创益大赛获奖团队风采:做一个中国特色的.Net源代码社区
- 从Paxos到ZooKeeper-一、分布式架构
- XML的四种解析方式
- POJ 2187: Beauty Contest(旋转卡)
- 浅析JavaScript的字符串查找函数:indexOf和search
- Linux引导流程(第二版)
- [转载] Relearning to Learn - 学会学习
- JavaScript数组删除指定元素
- 【转】Angular学习总结--很详细的教程
- pandas 级联 concat append
- tomcat 防火墙如何设置
- Android Edittext聚焦时输入法挡住了EditText输入框的两种解决方案
- python程序打包
- mysql -- 远程访问mysql的解决方案
- 蓝桥杯 - G将军有一支训练有素的军队 - [树形DP]
- Linux新建用户 useradd&;groupadd
- Linux 如何将一个文件夹的所有内容授权给某一个用户
- springmvc 使用jq传递json数据时出现415错误
- 16_常用API_第16天(正则表达式、Date、DateFormat、Calendar)_讲义