Algorithm Princeton part II (week5)

Week5真心是拖了好久好久，上课的内容也是很难。。大家多多努力吧。先上图

说说我的思路吧，根据hint上的提示，先搞清楚BoggleBoard，其实就是大致了解它长啥样。
我在构造dict的时候走了点弯路，一开始用了TrieST，然后String key的最后一个character存放分值，当时以为这样找到string后直接搞出值很牛，后来发现在getAllValidWords返回String就行了，而scoreOf再去找分值。这里应该先看完所有的API然后再决定dictionary的类型。
最后我确定用TrieSET,这个可以在最后一个character存放isString，来判断时候为String。getAllValidWords方法中，先将board变成Graph，和之前学过做过的比较相似，把各个vertices之间的edge加上。
接着就到了关键的部分，我们是要用dfs找到合适的string，长度大于2，并且存在dictionary中。这里如果发现下一个char在dictionary trie的next[]里没有，那就不用继续找下去了。这里我是在trie改了R，以及加上了一些field与method，可以增减char，并得到String。（一开始我也打算在BoggleSolver里面写，但发现Node中的next是private的不能拿到外面来，所以还不如重新写一下trie，用新的API去写Solver，这样看起来更加清晰）。
关于Q的问题，如果dfs中下一个char是Q，那么就要检查下下个是不是U，是U就加进去，不是U则返回（不可能继续了），在退出的时候也要注意减去两个char，正常的是减去一个char。（可能这么说不太明白，但写的时候注意吧，之前没检查出来）

好久没上这门算法课了，5.30就要截止了。想想还是得硬着头皮把最后这两个作业给做完。视频下了以后还可以看。
这次作业不难，但是挺繁琐，就和上次那个baseball illumination一样，你得在写代码之前就想好用什么数据结构来解决什么问题。
我一开始用的是自己写的递归。同样，为了避免DFS到已经扫描过的点，我愚蠢的把已经遍历的点放进了链表，进入的时候先遍历链表，看看是否已经有了该节点。退出的时候把尾结点删除就好了。
然后词典用什么数据结构存储。因为我发现结点不需要存储什么value，所以就直接用了 TrieSET,相应字符串尾结点就为true即可。然后存储词典的时候，我最后决定不需要考虑QU的问题。如果碰到了Q，最节约的方法是，往后跳两格，因为这个作业就是默认Q后面一定跟着U。但其实把U插入在Q后面，也不会占用多少资源。然后就成功把词典存储在了TrieSET中。
接着，我之前的思路就是自己写递归，然后后来发现链表太影响资源了，就打算自己重写一个布尔数组。不停地重置。后来想想，还是先上这里看下大神们什么思路再说吧。。。
于是看到了说用图。因为作业的提示里面说没必要用图。我一开始也没想到用图。后来想到了用图，又有一个问题。DFS里面，每个节点一定只能被遍历一次。但在这道题目的情景里面不是。于是我发现我思维定式了。我总是觉得只能一成不变得使用网上提供的类，后来发现可以改。那么就把重置布尔数组的操作全部加了进去。然后整个作业就差不多了。
这次作业代码量不多。首先拿TrieSET存储字典。并且把R改成26. 之后的 char[c]  其中一部分改成 char[c - 65]。然后根据board生成图。然后生成DFS类来处理这个图。改写其中的dfs方法。最关键的就是重置布尔数组。还有就是按照他的规则来进行相应的处理。然后将符合条件的字符串加入HashSet中。返回回去。 score方法就比较简单了。
还有个注意的地方。我一开始写好程序的时候发现特别慢。后来上来看了大家的评论，发现的确还是有一个无意义的工作。就是根据prefix确定之后是否有以此prefix开头的字符串。我当时偷懒了，直接调用了他的方法。然后如果返回的是null，那就代表没有。但其实只需要看next char对应在next[]中是否为空。如果是空的，就代表没有以此开头的字符串。
差不多就这样了。
PS：毕业季事情真他妈多啊。

czbnlzd920706 发表于 2015-5-24 22:32
好久没上这门算法课了，5.30就要截止了。想想还是得硬着头皮把最后这两个作业给做完。视频下了以后还可以看 ...

哦，对了。没能拿满分是因为最后一个测试过不了。
test scoreOf() on various dictionaries
  *  dictionary = dictionary-algs4.txt
      -  failed on trial 1 of 1000
      -  word = BARBER
      -  student   score = 3
      -  reference score = 0
  *  dictionary = dictionary-common.txt
      -  failed on trial 1 of 5000
      -  word = SUBPROBLEM
      -  student   score = 11
      -  reference score = 0
  *  dictionary = dictionary-shakespeare.txt
      -  failed on trial 3 of 10000
      -  word = BELOVE
      -  student   score = 3
      -  reference score = 0
  *  dictionary = dictionary-nursery.txt
  *  dictionary = dictionary-yawl.txt
      -  failed on trial 16 of 20000
      -  word = TIMANDRA
      -  student   score = 11
      -  reference score = 0
==> FAILED

不知道什么情况，想想算了。

最后两个timing实在是搞不定了。心塞。
想知道isPrefix和dfs从recursive变成non-recursive真的有差么？我自己算了时间还是通不过。
虽然我知道的确重复计算了很多subroutine. 但是，每次都附带了挺多状态，感觉用recursive还挺好的，每一个subroutine维护一个visited的集合。代码看着还算干净。

Trie用的是tenacy search trie，自己稍微改写一下下了。感觉这个算法的关键就是基于当前的trie node和char是否存在subtrie （是否是valid prefix) ，如果不存在直接忽略这条路。感觉还是挺有意思的。第一次接触Trie，真的很震撼。

我是重写了TST

中间出去玩了几天，回来后断断续续写了2天，感觉自己还是太渣，一碰头到递归问题，就容易乱

谢谢你们！谢谢coursera！

这次作业上手倒是不难，但是优化过程实在是太揪心了，拿满分真心不容易

我认为你并不需要在dfs的时候判断prefix是Qu还是Q, 不管是什么，都可以判断是不是valid prefix

也可能是理解错了你的意思

letsdoit666 发表于 2015-5-4 15:16
中间出去玩了几天，回来后断断续续写了2天，感觉自己还是太渣，一碰头到递归问题，就容易乱

请问你recursive的方法timing还可以通过？好神奇

我认为你并不需要在dfs的时候判断prefix是Qu还是Q, 不管是什么，都可以判断是不是valid prefix

也可能是理解错了你的意思