高频算法面试题(字符串) leetcode 212. 单词搜索 II

栏目: 编程工具 · 发布时间: 5年前

内容简介:给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。说明:

leetcode 212. 单词搜索 II

给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

输入: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

输出: ["eat","oath"]

说明:

你可以假设所有输入都由小写字母 a-z 组成。

首先,这道题我们可以构建一个Trie树。

但是,我选择递归。

虽然慢,但是爽。

这次的代码写得欠收拾,但是从0到1解决了,从1到多还不是吃豆芽一样。

走起:

func findWords(board [][]byte, words []string) []string {
    //第一维
    lb := len(board)
    //第二维,命名请忽略哈哈
    lbb := len(board[0])
    //依旧闭包上瘾
    var DFS func (string,int,int,[][]bool) bool 
    DFS = func (s string,x int,y int, flag [][]bool) bool{
        if len(s) == 0 {
            return true
        }
        //越界,或者当前字母不满足构成单词,或者当前字母在当前单词已被使用过就返回false
        if x < 0 || x >= lbb || y < 0 || y >= lb || s[0] != board[y][x] || flag[y][x]{
            return false
        }
        //我们将当前满足条件的字母记忆化
        flag[y][x] = true
        //这里是重点,我们向四个方向分别递归,只要有一个方向能满足就可以返回true
        if DFS (s[1:],x,y+1,flag) || DFS (s[1:],x-1,y,flag) || DFS (s[1:],x,y-1,flag) || DFS (s[1:],x+1,y,flag){
            return true
        }
        //不影响下次
        flag[y][x] = false
        return false
    }
    
    re := []string{}
    for _, v := range words {
        //这里我想的是每个单词都要重新来一个二维数组判断字母是否重复。看着很不顺眼
        flag := [][]bool{}
        for i:=0; i<lb; i++ {
            flag = append(flag,make([]bool,lbb))
        }
        //这里因为不想使用goto,所以来了个二级跳
        needBreak := false
        for i:=0; i<lb; i++ {
            for j:=0; j<lbb; j++ {
                if DFS(v,j,i,flag) {
                    re = append(re,v)
                    needBreak= true
                    break
                }
            }
            if needBreak{
                break
            }
        }
    }
    return re
}

这次的代码比较不满意,需要完善的地方太多了,但是我依然觉得思路更重要一些。当然了,对一个极客来说,手写一个Trie树,获得最好的性能才是目标。OK,以后再说咯哈哈。

算法梦想家,来跟我一起玩算法,玩音乐,聊聊文学创作,咱们一起天马行空!

高频算法面试题(字符串) leetcode 212. 单词搜索 II


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Web2.0策划指南

Web2.0策划指南

艾美 / 2009-11 / 32.00元

《Web2.0策划指南(影印版)》是讲述战略的。书中的示例关注的是Web 20的效率,而不聚焦于技术。你将了解到这样一个事实:创建Web 20业务或将Web 20战略整合到业务中,意味着创建一个吸引人们前来访问的在线站点,让人们愿意到这里来共享他们的思想、见闻和行动。当人们通过Web走到一起时,可能得到总体远远大于各部分和的结果。随着传统的“口碑传诵”助推站点高速成长,客户本身就能够帮助建立站点。......一起来看看 《Web2.0策划指南》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具