LintCode问题图解-23

2017-11-01 本文已影响5人 billliu_0d62

本文准备讲解1个算法编程问题，这个算法编程问题来自LintCode平台。不了解.LintCode平台的读者可以阅读笔者文章（在线编程平台推荐-LeetCode）。问题的英文版本描述如下：

Minimum Window Substring

For a string source and a string target, find the minimum window in source which will contain all the characters in target.

Notice

If there is no such window in source that covers all characters in target, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in source.

Clarification

Should the characters in minimum window has the same order in target?

Not necessary.

Example

For source ="ADOBECODEBANC", target ="ABC", the minimum window is "BANC".

最短子串

给定一个字符串 source 和一个目标字符串 target，在字符串 source 中找到包括所有目标字符串字母的最短子串。

注意事项

如果在 source 中没有这样的子串，返回 ""。

该问题有2个特殊的地方：需要找到包括所有目标字符串字母的子串和需要找到最短子串。找到包括所有目标字符串字母的子串需要设计功能函数。功能函数需要关注每个目标串字母的位置：例如 "BANC" 可以覆盖目标串 "ABC"。找到最短子串的方法也比较特殊。公布的算法无法处理目标串字符重复出现。

简单的算法