首页 > 代码库 > LeetCode 30 Substring with Concatenation of All Words（确定包含所有子串的起始下标）
LeetCode 30 Substring with Concatenation of All Words（确定包含所有子串的起始下标）
题目链接： https://leetcode.com/problems/substring-with-concatenation-of-all-words/?tab=Description
在字符串s中找到包含字符串数组words所有子串连续组合的起始下标（words中的子串排列顺序前后不计但是需要相连在s中不能存在其他字符）
参考代码 :
package leetcode_50;import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;/*** * * @author pengfei_zheng * 匹配words所有元素 */public class Solution30 { public List<Integer> findSubstring(String s, String[] words) { List<Integer> result = new ArrayList<Integer>(); int wordLength = words[0].length(), patternLength = wordLength * words.length; if (patternLength > s.length()) { return result; } // array[0] stores the word count in the given pattern // array[1] stores the word count in the actual string int[][] wordCountArr = new int[2][words.length]; // This map is used to maintain the index of the above array Map<String, Integer> wordCountIndexMap = new HashMap<String, Integer>(); // storing the word counts in the given patter. array[0] is populated for (int i = 0, idx = 0; i < words.length; i++) { if (wordCountIndexMap.containsKey(words[i])) { wordCountArr[0][wordCountIndexMap.get(words[i])]++; } else { wordCountIndexMap.put(words[i], idx); wordCountArr[0][idx++]++; } } // this is required to cover use case when the given string first letter // doesnt corresponds to any matching word. for (int linearScan = 0; linearScan < wordLength; linearScan++) { int left = linearScan, right = linearScan, last = s.length() - wordLength, wordMatchCount = words.length; // reset word counts for the given string Arrays.fill(wordCountArr[1], 0); // this logic same as minimum window problem while (right <= last) { while (wordMatchCount > 0 && right <= last) { String subStr = s.substring(right, right + wordLength); if (wordCountIndexMap.containsKey(subStr)) { int idx = wordCountIndexMap.get(subStr); wordCountArr[1][idx]++; if (wordCountArr[0][idx] >= wordCountArr[1][idx]) { wordMatchCount--; } } right += wordLength; } while (wordMatchCount == 0 && left < right) { String subStr = s.substring(left, left + wordLength); if (wordCountIndexMap.containsKey(subStr)) { // this check is done to make sure the sub string has // only the given words. if ((right - left) == patternLength) { result.add(left); } int idx = wordCountIndexMap.get(subStr); // if this condition is satisfied, that means now we // need to find the removed word in the remaining string if (--wordCountArr[1][idx] < wordCountArr[0][idx]) { wordMatchCount++; } } left += wordLength; } } } return result; }}
LeetCode 30 Substring with Concatenation of All Words（确定包含所有子串的起始下标）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。