本文共 2785 字，大约阅读时间需要 9 分钟。

LeetCode刷题：30. Substring with Concatenation of All Words

原题链接：

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.

Example 1:

Input:

  s = "barfoothefoobarman",   words = ["foo","bar"] Output: [0,9] Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively. The output order does not matter, returning [9,0] is fine too. Example 2:

Input:

  s = "wordgoodgoodgoodbestword",   words = ["word","good","best","word"] Output: []  

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

 

示例 1：

输入：

  s = "barfoothefoobarman",   words = ["foo","bar"] 输出：[0,9] 解释： 从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。 输出的顺序不重要, [9,0] 也是有效答案。 示例 2：

输入：

  s = "wordgoodgoodgoodbestword",   words = ["word","good","best","word"] 输出：[]

---

算法设计

package com.bean.algorithmbasic;import java.util.ArrayList;import java.util.HashMap;import java.util.List;/* * Substring with Concatenation of All Words * */public class LeetCode_30 {	public List
   
     findSubstring(String s, String[] words) {		List
    
      result = new ArrayList<>();		int wordSize = words.length;		if (wordSize == 0) {			return result;		}		// words 数组中每个字符的长度都一致, 取第一个		int wordLength = words[0].length();		// 字符数组有可能有重复的, 使用 allWordMap 存放每个 word 出现的次数		HashMap
     
       allWordMap = new HashMap<>();		for (String word : words) {			allWordMap.put(word, allWordMap.getOrDefault(word, 0) + 1);		}		for (int i = 0; i < s.length() - wordSize * wordLength + 1; i++) {			HashMap
      
        hashMap = new HashMap<>();			// 单趟循环中, 成功匹配的次数			int num = 0;			while (num < wordSize) {				// 根据查找字符的长度进行截断				String word = s.substring(i + num * wordLength, i + (num + 1) * wordLength);				if (allWordMap.containsKey(word)) {					hashMap.put(word, hashMap.getOrDefault(word, 0) + 1);					// 还有可能超过 words 中原来的数量					if (hashMap.get(word) > allWordMap.get(word)) {						break;					}				} else {					// 如果没有查询到, 跳过这次循环, 查找下一个字符					break;				}				num++;			}			if (num == wordSize) {				result.add(i);			}		}		return result;	}	public static void main(String[] args) {		// TODO Auto-generated method stub		/*		 * Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9]		 * Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar"		 * respectively. The output order does not matter, returning [9,0] is fine too.		 */		LeetCode_30 leetCode30 = new LeetCode_30();				String s="barfoothefoobarman";		String[] words= {"foo","bar"};				List
       
         list = leetCode30.findSubstring(s, words);		System.out.println(list);			}}
       
      
     
    
   

程序运行结果：

[0, 9]

 

转载地址：http://fntdi.baihongyu.com/