【LeetCode-面试算法经典-Java实现】【030-Substring with Concatenation of All Words（串联全部单词的子串）】...

一时失言乱红尘 2021-12-15 12:27 162阅读 0赞

# **[【030-Substring with Concatenation of All Words（串联全部单词的子串）】][030-Substring with Concatenation of All Words]** #

--------------------

## **[【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】][LeetCode-_-Java]** ##

## **原题** ##

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.  
　　For example, given:  
　　s: `"barfoothefoobarman"`  
　　words: `["foo", "bar"]`  
　　You should return the indices: `[0,9]`.  
　　(order does not matter).

## **题目大意** ##

给定一个字符串s和一个字符串数组words，wrods中的字符串长度都相等。找出s中全部的子串恰好包括words中全部字符各一次，返回子串的起始位置。

## **解题思路** ##

把words转化为一个HashMap

## **代码实现** ##

算法实现类

import java.util.*;
    
    public class Solution {
    
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> list = new ArrayList<Integer>();
            if (words.length == 0) return list;
            int wLen = words[0].length();
            int len = s.length();
            if (len < wLen * words.length) return list;
            Map<String, Integer> mapW = new HashMap<String, Integer>();
            for (String word : words)
                mapW.put(word, mapW.containsKey(word) ? mapW.get(word) + 1 : 1);
            for (int start = 0; start < wLen; start++) {
                int pos = start;
                int tStart = -1;
                Map<String, Integer> mapT = new HashMap<String, Integer>(mapW);
                while (pos + wLen <= len) {
                    String cand = s.substring(pos, pos + wLen);
                    if (!mapW.containsKey(cand)) {
                        if (tStart != -1) mapT = new HashMap<String, Integer>(mapW);
                        tStart = -1;
                    } else if (mapT.containsKey(cand)) {
                        tStart = tStart == -1 ?

`pos : tStart; if (mapT.get(cand) == 1) mapT.remove(cand); else mapT.put(cand, mapT.get(cand) - 1); if (mapT.isEmpty()) list.add(tStart); } else { while (tStart < pos) { String rCand = s.substring(tStart, tStart + wLen); if (cand.equals(rCand)) { tStart += wLen; if (mapT.isEmpty()) list.add(tStart); break; } tStart += wLen; mapT.put(rCand, mapT.containsKey(rCand) ? mapT.get(rCand) + 1 : 1); } } pos += wLen; } } return list; } }`

## **评測结果** ##

**点击图片，鼠标不释放，拖动一段位置，释放后在新的窗体中查看完整图片。**

![这里写图片描写叙述][20150718182046742]

## **特别说明** ##

### **欢迎转载。转载请注明出处【[http://blog.csdn.net/derrantcm/article/details/47064933][http_blog.csdn.net_derrantcm_article_details_47064933]】** ###

转载于:https://www.cnblogs.com/yutingliuyl/p/7259295.html

[030-Substring with Concatenation of All Words]: http://blog.csdn.net/DERRANTCM/article/details/47064933
[LeetCode-_-Java]: http://blog.csdn.net/derrantcm/article/details/46905087
[20150718182046742]: /images/20211214/0d6fad64c7d84826aa773e8398714885.png
[http_blog.csdn.net_derrantcm_article_details_47064933]: http://blog.csdn.net/derrantcm/article/details/47064933