一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3087|回复: 6
收起左侧

[Leetcode] 请教一题Substring with Concatenation of All Words

[复制链接] |试试Instant~ |关注本帖
wendychueng 发表于 2014-6-23 15:53:28 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 wendychueng 于 2014-6-23 02:56 编辑

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).


这个是discuss里面一个人写的算法,看不太懂中间那个if... else if... else... 有没有同学可以解释一下? 谢谢!

//use hash table to store the list of words L
//for each m char in the string, check if it is a valid word

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        vector<int> result;
        map<string, int> cntL;
        map<string, int> cn;
        int n = S.length();
        int wordlen = L[0].length();
        int listsize = L.size();
        int count = 0;    // number of words in the list
        //store the list of words in hash table
        for(int i=0; i<listsize; i++)
        {
            //if this key has not been occupied
            if(cn.count(L) == 0)
        
    {
                cn[L] = 1;
                count++;
            }
            else
            {
                cn[L] += 1;
                count++;
            }
        }

        string tr, du;
        int r = 0;
        int st = 0;

        for(int j=0; j<wordlen; j++)   //for each char in a word
        { r = 0; st = j;
          for(int i=j; i<n; i += wordlen)  //check the string for every word length substring
          {
              tr = S.substr(i, wordlen);  //copy the next m char in the string
              if(cn.count(tr) == 0 || cn[tr] == 0)  //?? if this is not a valid word
              {
                  cntL.clear();
                  r = 0;
                  st = i+wordlen;
              }
              else if(cntL[tr] < cn[tr]) // ???
              {
                  cntL[tr] += 1;
                  r++;
              }
              else
              {
                  du = S.substr(st, wordlen);
                  while(du != tr)
                  {
                      cntL[du]--;
                      r--;
                      st += wordlen;
                      du = S.substr(st, wordlen);
                  }
                  st += wordlen;
              }
              if(r == count)   //if r == count meaning all the words have appeared
              {
                  result.push_back(st);
                  du = S.substr(st, wordlen);
                  cntL[du]--;
                  r--;
                  st += wordlen;
              }
          }
          cntL.clear();
        }
        sort(result.begin(), result.end());
        return result;
    }
};

 楼主| wendychueng 发表于 2014-6-24 02:27:53 | 显示全部楼层
做过这题的同学来说一下思路也行啊
回复 支持 反对

使用道具 举报

 楼主| wendychueng 发表于 2014-6-27 04:15:33 | 显示全部楼层
做过这题的同学来说一下思路吧
回复 支持 反对

使用道具 举报

wizard19900509 发表于 2014-6-28 00:17:30 | 显示全部楼层
这题基本就是暴力解吧
用L里面的词建一个字典 c++就是map 记录每个出现的词以及出现几次 然后遍历字符串所有可能的起点 每个起点扫一遍 一旦发现不在字典中的词或者出现频率超过字典里的值 就退出进行下一个循环即可
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-28 01:12:04 | 显示全部楼层
本帖最后由 readman 于 2014-6-28 01:13 编辑

这题我做的方法和以上不太一样.
我把L排序, 然后在一个loop中用L的长度扫S. 每次用boyer moore看L里的字串是不是substring, 不过复杂度好高..O(outer loop) * O(n+m) bm
回复 支持 反对

使用道具 举报

xiaobenben 发表于 2015-1-21 13:48:51 | 显示全部楼层
不太明白题意,有人能解释下不?
回复 支持 反对

使用道具 举报

Sayings 发表于 2016-7-20 11:35:35 | 显示全部楼层
wizard19900509 发表于 2014-6-28 00:17
这题基本就是暴力解吧
用L里面的词建一个字典 c++就是map 记录每个出现的词以及出现几次 然后遍历字符串所 ...

暴力解现在超时了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 12:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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