找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2677|回复: 5
收起左侧

[米群网刷题小分队] 【LeetCode】【Word Search】

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 11-27-2014 02:48 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
快速通道:
https://oj.leetcode.com/problems/word-search/

Given a 2D board and a word, find if the word exists in the grid.The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.


建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                         汇总贴 传送门
==================================

本帖被以下淘专辑推荐:

发表于 11-27-2014 01:31 PM | 显示全部楼层

思路:dfs
代码:
  1. class Solution {
  2. public:
  3.     bool have(vector<vector<char> > &board, int m,int n, int x,int y,string word,int now) {
  4.         if (now >= word.size()) {
  5.             return true;
  6.         }
  7.         if ((x >= m) || (x < 0) || (y >= n) || (y < 0) || (board[x][y] != word[now])) {
  8.             return false;
  9.         }
  10.         board[x][y] = '!';
  11.         bool r = have(board, m ,n , x - 1, y, word, now + 1) ||  have(board, m ,n , x + 1, y, word, now + 1) ||  have(board, m ,n , x, y - 1, word, now + 1) ||  have(board, m ,n , x, y + 1, word, now + 1);
  12.         board[x][y] = word[now];
  13.         return r;
  14.         
  15.     }
  16.     bool exist(vector<vector<char> > &board, string word) {
  17.         // IMPORTANT: Please reset any member data you declared, as
  18.         // the same Solution instance will be reused for each test case.
  19.         if (board.empty()) {
  20.             return false;
  21.         }
  22.         int m = board.size(), n = board[0].size();
  23.         for (int i = 0; i < m; ++i) {
  24.             for (int j = 0; j < n; ++j) {
  25.                 if (have(board, m, n, i, j, word, 0)) {
  26.                     return true;
  27.                 }
  28.             }
  29.         }
  30.         return false;
  31.         
  32.         
  33.     }
  34. };
复制代码

复杂度分析:指数的 大概4^len
细节和陷阱:不能重复走
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 12-9-2014 08:08 PM | 显示全部楼层
思路和曹神的一样,只是因为要遍历整个board数组,我觉得时间复杂度是O(mn*4^len),m,n分别是board的行列元素个数。我的空间复杂度是O(mn),因为我用了额外的数组visited来存储节点是否已经访问过,这样也导致了另一个问题,当以传值方式传递visited数组时,浪费时间,time limit exceed,改为传引用方式就无问题。而曹神更改board的方法时间和空间都有提高,高明!!!

补充内容 (12-9-2014 09:50 PM):
另外,曹神有空可以讲一下有没有更好的解存在啊

补充内容 (12-9-2014 10:49 PM):
我的代码去掉visited数组后,leetcode运行时间从140ms降到了88ms
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表