查找包含另一个字符串中字符串的所有字符的最小窗口的长度
最近我接受了采访。 我做得不好因为我遇到了以下问题
假设给出了一个序列：ADCBDABCDACD和搜索序列如下：ACD
任务是在给定字符串中查找包含保留顺序的搜索字符串的所有字符的开始和结束索引。
输出 ：假设索引从1开始：
开始索引10结束索引12
解释 ：
1.start / end index分别不是1/3，因为虽然它们包含字符串但是没有维护订单
2.start / end index分别不是1/5，因为它们虽然包含顺序的字符串，但长度不是最佳的
3.start / end index分别不是6/9，因为它们虽然包含顺序中的字符串但长度不是最佳的
请详细说明如何查找包含给定字符串中所有字符的最小子字符串？ 。
但由于订单未得到维护，上述问题不同。 我仍在努力维持索引。 任何帮助，将不胜感激 。 谢谢
我试着写一些简单的c代码来解决这个问题：
更新：
我编写了一个search函数，以正确的顺序查找所需的字符，返回窗口的长度并将窗口起始点存储到“ ìnt * startAt 。 该函数处理从指定的起始点int start到它的结尾的给定hay的子序列
算法的其余部分位于main ，其中所有可能的子序列都通过小优化进行测试：我们开始在前一个窗口的起始点之后查找下一个窗口，因此我们跳过一些不必要的转弯。 在此过程中，我们会跟踪“直到最佳解决方案”
复杂度为O（n * n / 2）
UPDATE2：
已删除不必要的依赖项，对strlen(...)不必要的后续调用已被传递给search(...)的大小参数替换search(...)
#include // search for single occurrence int search(const char hay[], int haySize, const char needle[], int needleSize, int start, int * startAt) { int i, charFound = 0; // search from start to end for (i = start; i < haySize; i++) { // found a character ? if (hay[i] == needle[charFound]) { // is it the first one? if (charFound == 0) *startAt = i; // store starting position charFound++; // and go to next one } // are we done? if (charFound == needleSize) return i - *startAt + 1; // success } return -1; // failure } int main(int argc, char **argv) { char hay[] = "ADCBDABCDACD"; char needle[] = "ACD"; int resultStartAt, resultLength = -1, i, haySize = sizeof(hay) - 1, needleSize = sizeof(needle) - 1; // search all possible occurrences for (i = 0; i < haySize - needleSize; i++) { int startAt, length; length = search(hay, haySize, needle, needleSize, i, &startAt); // found something? if (length != -1) { // check if it's the first result, or a one better than before if ((resultLength == -1) || (resultLength > length)) { resultLength = length; resultStartAt = startAt; } // skip unnecessary steps in the next turn i = startAt; } } printf("start at: %d, length: %d\n", resultStartAt, resultLength); return 0; }
从字符串的开头开始。
如果遇到A，则标记位置并将其推入堆栈。 之后，继续按顺序检查字符，直到
1.如果遇到A，请将A的位置更新为当前值。
2.如果遇到C，请将其推入堆栈。
遇到C之后，再次按顺序检查字符，直到
1.如果遇到D，请擦除包含A和C的堆栈，并为该子序列标记从A到D的分数。
2.如果遇到A，则启动另一个堆栈并标记此位置。
2A。 如果现在遇到C，则擦除较早的堆栈并保留最近的堆栈。
2B。 如果遇到D，则擦除旧堆栈并标记分数并检查它是否小于当前最佳分数。
继续这样做，直到你到达字符串的末尾。
伪代码可以是这样的：
Initialize stack = empty; Initialize bestLength = mainString.size() + 1; // a large value for the subsequence. Initialize currentLength = 0; for ( int i = 0; i < mainString.size(); i++ ) { if ( stack is empty ) { if ( mainString[i] == 'A' ) { start a new stack and push A on it. mark the startPosition for this stack as i. } continue; } For each of the stacks ( there can be at most two stacks prevailing, one of size 1 and other of size 0 ) { if ( stack size == 1 ) // only A in it { if ( mainString[i] == 'A' ) { update the startPosition for this stack as i. } if ( mainString[i] == 'C' ) { push C on to this stack. } } else if ( stack size == 2 ) // A & C in it { if ( mainString[i] == 'C' ) { if there is a stack with size 1, then delete this stack;// the other one dominates this stack. } if ( mainString[i] == 'D' ) { mark the score from startPosition till i and update bestLength accordingly. delete this stack. } } } }
我使用单个队列修改了我之前的建议，现在我相信这个算法以O(N*m)时间运行：
FindSequence(char[] sequenceList) { queue startSeqQueue; int i = 0, k; int minSequenceLength = sequenceList.length + 1; int startIdx = -1, endIdx = -1; for (i = 0; i < sequenceList.length - 2; i++) { if (sequenceList[i] == 'A') { startSeqQueue.queue(i); } } while (startSeqQueue!=null) { i = startSeqQueue.enqueue(); k = i + 1; while (sequenceList.length < k && sequenceList[k] != 'C') if (sequenceList[i] == 'A') i = startSeqQueue.enqueue(); k++; while (sequenceList.length < k && sequenceList[k] != 'D') k++; if (k < sequenceList.length && k > minSequenceLength > k - i + 1) { startIdx = i; endIdx = j; minSequenceLength = k - i + 1; } } return startIdx & endIdx }
我之前的（O（1）记忆）建议：
FindSequence(char[] sequenceList) { int i = 0, k; int minSequenceLength = sequenceList.length + 1; int startIdx = -1, endIdx = -1; for (i = 0; i < sequenceList.length - 2; i++) if (sequenceList[i] == 'A') k = i+1; while (sequenceList.length < k && sequenceList[k] != 'C') k++; while (sequenceList.length < k && sequenceList[k] != 'D') k++; if (k < sequenceList.length && k > minSequenceLength > k - i + 1) { startIdx = i; endIdx = j; minSequenceLength = k - i + 1; } return startIdx & endIdx; }
这是我的版本。 它跟踪可能的候选人以获得最佳解决方案。 对于干草中的每个角色，它会检查此角色是否按每个候选人的顺序排列。 然后它选择最短的候选人。 相当简单。
class ShortestSequenceFinder { public class Solution { public int StartIndex; public int Length; } private class Candidate { public int StartIndex; public int SearchIndex; } public Solution Execute(string hay, string needle) { var candidates = new List(); var result = new Solution() { Length = hay.Length + 1 }; for (int i = 0; i < hay.Length; i++) { char c = hay[i]; for (int j = candidates.Count - 1; j >= 0; j--) { if (c == needle[candidates[j].SearchIndex]) { if (candidates[j].SearchIndex == needle.Length - 1) { int candidateLength = i - candidates[j].StartIndex; if (candidateLength < result.Length) { result.Length = candidateLength; result.StartIndex = candidates[j].StartIndex; } candidates.RemoveAt(j); } else { candidates[j].SearchIndex += 1; } } } if (c == needle[0]) candidates.Add(new Candidate { SearchIndex = 1, StartIndex = i }); } return result; } }
它以O（n * m）运行。
这是我在Python中的解决方案。 它返回索引，假设0索引序列。 因此，对于给定的示例，它返回(9, 11)而不是(10, 12) 。 显然(10, 12)如果你愿意(10, 12)可以很容易地将其改变为返回(10, 12) 。
def solution(s, ss): S, E = [], [] for i in xrange(len(s)): if s[i] == ss[0]: S.append(i) if s[i] == ss[-1]: E.append(i) candidates = sorted([(start, end) for start in S for end in E if start <= end and end - start >= len(ss) - 1], lambda x,y: (x[1] - x[0]) - (y[1] - y[0])) for cand in candidates: i, j = cand[0], 0 while i <= cand[-1]: if s[i] == ss[j]: j += 1 i += 1 if j == len(ss): return cand
用法：
>>> from so import solution >>> s = 'ADCBDABCDACD' >>> solution(s, 'ACD') (9, 11) >>> solution(s, 'ADC') (0, 2) >>> solution(s, 'DCCD') (1, 8) >>> solution(s, s) (0, 11) >>> s = 'ABC' >>> solution(s, 'B') (1, 1) >>> print solution(s, 'gibberish') None
我认为时间复杂度为O（p log（p））其中p是序列中引用search_sequence[0]和search_sequence[-1]的索引对的数量，其中search_sequence[0]的索引小于search_sequence[-1]的索引，因为它使用O（n log n）算法对这些p对进行排序。 但话说回来，我最后的子串迭代可能完全掩盖了排序步骤。 我不太确定。
它可能具有最坏情况的时间复杂度，其以O（n * m）为界，其中n是序列的长度，m是搜索序列的长度，但此刻我不能想到最坏情况的例子。
这是我在Java中的O（m * n）算法：
class ShortestWindowAlgorithm { Multimap charToNeedleIdx; // Character -> indexes in needle, from rightmost to leftmost | Multimap is a class from Guava int[] prefixesIdx; // prefixesIdx[i] -- rightmost index in the hay window that contains the shortest found prefix of needle[0..i] int[] prefixesLengths; // prefixesLengths[i] -- shortest window containing needle[0..i] public int shortestWindow(String hay, String needle) { init(needle); for (int i = 0; i < hay.length(); i++) { for (int needleIdx : charToNeedleIdx.get(hay.charAt(i))) { if (firstTimeAchievedPrefix(needleIdx) || foundShorterPrefix(needleIdx, i)) { prefixesIdx[needleIdx] = i; prefixesLengths[needleIdx] = getPrefixNewLength(needleIdx, i); forgetOldPrefixes(needleIdx); } } } return prefixesLengths[prefixesLengths.length - 1]; } private void init(String needle) { charToNeedleIdx = ArrayListMultimap.create(); prefixesIdx = new int[needle.length()]; prefixesLengths = new int[needle.length()]; for (int i = needle.length() - 1; i >= 0; i--) { charToNeedleIdx.put(needle.charAt(i), i); prefixesIdx[i] = -1; prefixesLengths[i] = -1; } } private boolean firstTimeAchievedPrefix(int needleIdx) { int shortestPrefixSoFar = prefixesLengths[needleIdx]; return shortestPrefixSoFar == -1 && (needleIdx == 0 || prefixesLengths[needleIdx - 1] != -1); } private boolean foundShorterPrefix(int needleIdx, int hayIdx) { int shortestPrefixSoFar = prefixesLengths[needleIdx]; int newLength = getPrefixNewLength(needleIdx, hayIdx); return newLength <= shortestPrefixSoFar; } private int getPrefixNewLength(int needleIdx, int hayIdx) { return needleIdx == 0 ? 1 : (prefixesLengths[needleIdx - 1] + (hayIdx - prefixesIdx[needleIdx - 1])); } private void forgetOldPrefixes(int needleIdx) { if (needleIdx > 0) { prefixesLengths[needleIdx - 1] = -1; prefixesIdx[needleIdx - 1] = -1; } } }
它适用于每个输入，也可以处理重复的字符等。
这里有些例子：
public class StackOverflow { public static void main(String[] args) { ShortestWindowAlgorithm algorithm = new ShortestWindowAlgorithm(); System.out.println(algorithm.shortestWindow("AXCXXCAXCXAXCXCXAXAXCXCXDXDXDXAXCXDXAXAXCD", "AACD")); // 6 System.out.println(algorithm.shortestWindow("ADCBDABCDACD", "ACD")); // 3 System.out.println(algorithm.shortestWindow("ADCBDABCD", "ACD")); // 4 }
我没有在这里阅读每个答案，但我认为没有人注意到这只是局部成对序列比对的限制版本，其中我们只允许插入字符（而不是删除或替换它们）。 因此，它将通过Smith-Waterman算法的简化来解决，该算法仅考虑每个顶点2个案例（通过精确匹配字符或通过插入字符来到达顶点）而不是3个案例。 该算法为O（n ^ 2）。
这是我的解决方案。 它遵循一种模式匹配解决方案。 如果我错了，请评论/纠正我。
给定输入字符串，如问题ADCBDABCDACD 。 让我们首先计算出现A的指数。 假设基于零的索引，这应该是[0,5,9] 。
现在伪代码如下。
Store the indices of A in a list say *orders*.// orders=[0,5,9] globalminStart, globalminEnd=0,localMinStart=0,localMinEnd=0; for (index: orders) { int i =index; Stack chars=new Stack();// to store the characters i=localminStart; while(i< length of input string) { if(str.charAt(i)=='C') // we've already seen A, so we look for C st.push(str.charAt(i)); i++; continue; else if(str.charAt(i)=='D' and st.peek()=='C') localminEnd=i; // we have a match! so assign value of i to len i+=1; break; else if(str.charAt(i)=='A' )// seen the next A break; } if (globalMinEnd-globalMinStart
PS：这是伪代码和粗略的想法。 我很乐意纠正它并理解是否有错误。
AFAIC时间复杂度-O（n）。 空间复杂度O（n）