文档章节

[LeetCode]Substring with concatenation of all words

SamXCode
 SamXCode
发布于 2015/05/18 22:10
字数 721
阅读 28
收藏 0

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in wordsexactly once and without any intervening characters.

Analysis

同样可以采用滑动窗口法解决。在移动的过程中维护一个HashMap的字典,保存查找的字符串状况。

step 1.构建一个HashMap dict的字典,key-value对应words中的word和出现的次数。注意给定的words中可能多次出现同一个word。

step 2.设word的length为wLen(每个word的长度都相同),第一层循环wLen次,每次循环整个字符串。

step 3.第二层循环每次循环前进wLen位,遍历整个字符串,单次循环内次数为s.length()/wLen。这样两层循环就可以覆盖所有可能的字符串。用startIndex记录匹配字符串的开始位置,count记录匹配的字典字符串的个数。用另一个HashMap curMap维护当前匹配字符串中字典字符串的状况。通过比较dict和curMap的key-value来更新count和startIndex。注意:当前匹配的字典字符串在整个匹配字符串中出现的次数超出即curMap.get(sub) > dict.get(sub),那么startIndex应直接移动到该匹配的字典字符串后一次出现位置之后,count同样减小。

packagecom.samxcode.leetcode;
 
importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
 
/**
 * You are given a string, s, and a list of words, words, that are all of the same length. Find all
 * starting indices of substring(s) in s that is a concatenation of each word in words exactly once
 * and without any intervening characters.
 *
 * @author Sam
 *
 */
publicclassFindSubstring {
     
    publicstaticvoidmain(String[] args) {
        String[] words = {"a","b","a"};
        System.out.println(findSubstring("abababab", words));
    }
 
    publicstaticList<Integer> findSubstring(String s, String[] words) {
        List<Integer> res =newArrayList<Integer>();
        if(words.length ==0|| s.length() ==0) {
            returnres;
        }
        intwLen = words[0].length();
        // the count of special words displayed each loop
        intcount;
        // the start index each matching process
        intstartIndex;
        // put the given dictionary into hash map with each word's count
        HashMap<String, Integer> dict =newHashMap<String, Integer>();
        // dictionary in current matching process
        HashMap<String, Integer> curMap =newHashMap<String, Integer>();
        for(String word : words) {
            if(dict.containsKey(word))
                dict.put(word, dict.get(word) +1);
            else
                dict.put(word,1);
        }
        for(inti =0; i < wLen; i++) {
            count =0;
            startIndex = i;
            curMap.clear();
            for(intj = i; j <= s.length() - wLen; j += wLen) {
                // current word
                String sub = s.substring(j, j + wLen);
                if(dict.containsKey(sub)) {
                    // update current dictionary
                    if(curMap.containsKey(sub))
                        curMap.put(sub, curMap.get(sub) +1);
                    else
                        curMap.put(sub,1);
                    count++;
                    // check if count for current found word exceed given word count
                    if(curMap.get(sub) > dict.get(sub)) {
                        // shift the start index to the found word's next word and update the count
                        while(curMap.get(sub) > dict.get(sub)) {
                            String temp = s.substring(startIndex, startIndex + wLen);
                            curMap.put(temp, curMap.get(temp) -1);
                            startIndex += wLen;
                            count--;
                        }
                    }
                    // put the start index into result, shift index to next word, and update current
                    // dictionary and count
                    if(count == words.length) {
                        res.add(startIndex);
                        String temp = s.substring(startIndex, startIndex + wLen);
                        curMap.put(temp, curMap.get(temp) -1);
                        startIndex += wLen;
                        count--;
                    }
                }else{
                    curMap.clear();
                    startIndex = j + wLen;
                    count =0;
                }
 
            }
        }
        returnres;
    }
}

Complexity

第一层循环wLen次,第二层循环n/wLen次,所以时间复杂度O(n),空间复杂度O(d*l),s 字典大小,l 字典字符串长度

© 著作权归作者所有

SamXCode
粉丝 0
博文 5
码字总数 2336
作品 0
长沙
程序员
私信 提问
Leetcode——Substring with Concatenation of All Word

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in wo......

wikison
2016/03/01
10
0
leetcode python 030 Substring with Concatenation of All Words

## 您将获得一个字符串s,以及一个长度相同单词的列表。 ## 找到s中substring(s)的所有起始索引,它们只包含所有单词, ## eg:s: "barfoothefoobarman" words: ["foo", "bar"] ## return......

蚂蚁不在线
2018/07/29
0
0
【Leetcode】804. Unique Morse Code Words

Unique Morse Code Words Description International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-"......

xiagnming
2018/07/27
0
0
Leetcode第21题至第30题 思路分析及C++实现

笔者按照目录刷题,对于每一道题,力争使用效率最高(时间复杂度最低)的算法,并全部通过C++代码实现AC。(文中计算的复杂度都是最坏情况复杂度) 因为考虑到大部分读者已经在Leetcode浏览过题...

大雄的学习人生
2018/08/17
0
0
LeetCode 分类刷题—— Two Pointers

Two Pointers 的 Tips: 双指针滑动窗口的经典写法。右指针不断往右移,移动到不能往右移动为止(具体条件根据题目而定)。当右指针到最右边以后,开始挪动左指针,释放窗口左边界。第 3 题,第...

一缕殇流化隐半边冰霜
07/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Jenkins World 贡献者峰会及专家答疑展位

本文首发于:Jenkins 中文社区 原文链接 作者:Marky Jackson 译者:shunw Jenkins World 贡献者峰会及专家答疑展位 本文为 Jenkins World 贡献者峰会活动期间的记录 Jenkins 15周岁啦!Jen...

Jenkins中文社区
27分钟前
8
0
杂谈:面向微服务的体系结构评审中需要问的三个问题

面向微服务的体系结构如今风靡全球。这是因为更快的部署节奏和更低的成本是面向微服务的体系结构的基本承诺。 然而,对于大多数试水的公司来说,开发活动更多的是将现有的单块应用程序转换为...

liululee
42分钟前
7
0
OSChina 周二乱弹 —— 我等饭呢,你是不是来错食堂了?

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @ 自行车丢了:给主编推荐首歌 《クリスマスの夜》- 岡村孝子 手机党少年们想听歌,请使劲儿戳(这里) @烽火燎原 :国庆快来,我需要长假! ...

小小编辑
今天
433
9
玩转 Springboot 2 之热部署(DevTools)

Devtools 介绍 SpringBoot 提供了热部署的功能,那啥是热部署累?SpringBoot官方是这样说的:只要类路径上的文件发生更改,就会自动重新启动应用程序。在IDE中工作时,这可能是一个有用的功能...

桌前明月
今天
6
0
CSS--列表

一、列表标识项 list-style-type none:去掉标识项 disc:默认实心圆 circle:空心圆 squire:矩形 二、列表项图片 list-style-img: 取值:url(路径) 三、列表项位置 list-style-position:...

wytao1995
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部