Минимальная ширина окна в строке x, которая содержит все символы строки y
Найдите минимальную ширину окна в строке x, которая содержит все символы другой строки y. Например:
String x = "coobdafceeaxab"
String y = "abc"
Ответ должен быть 5, потому что самая короткая подстрока в x, которая содержит все три буквы из y, - это "bdafc".
Я могу представить себе наивное решение со сложностью O(n^2 * log(m)), где n = len(x) и m = len(y). Может ли кто-нибудь предложить лучшее решение? Спасибо.
Обновить: теперь подумайте об этом, если я изменю свой набор на tr1::unordered_map, тогда я могу сократить сложность до O(n^2), потому что вставка и удаление должны быть O(1).
Ответы
Ответ 1
время: O (n) (один проход)
пространство: O (k)
Вот как я это сделаю:
Создайте хэш-таблицу для всех символов из строки Y. (Я предполагаю, что все символы различаются в Y).
Первый проход:
Начните с первого символа строки X.
обновить хеш-таблицу, для exa: для ключа 'a' введите местоположение (скажем 1).
Продолжайте делать это, пока не получите все символы из Y (пока весь ключ в хеш-таблице не будет иметь значения).
Если вы снова получите некоторый символ, обновите его новое значение и удалите более старый.
Как только вы пройдете первый проход, получите наименьшее значение из хэш-таблицы и наибольшее значение.
Это минимальное окно, наблюдаемое до сих пор.
Теперь перейдите к следующему символу в строке X, обновите хэш-таблицу и посмотрите, появится ли у вас меньшее окно.
Изменить:
Давайте рассмотрим пример:
Строка x = "coobdafceeaxab"
Строка y = "abc"
Сначала инициализируйте хэш-таблицу из символов Y.
h [a] = -1
h [b] = -1
h [c] = -1
Теперь, Начните с первого символа X.
Первый символ - c, h [c] = 0
Второй символ (o) не является частью хэша, пропустите его.
..
Четвертый символ (b), h [b] = 3
..
Шестой символ (a), введите хэш-таблицу h [a] = 5.
Теперь все ключи из хэш-таблицы имеют некоторое значение.
Наименьшее значение равно 0 (с), а наибольшее значение - 5 (a), минимальное окно пока равно 6 (от 0 до 5).
Первый проход завершен.
Возьмите следующий символ. f не является частью хеш-таблицы, пропустите ее.
Следующий символ (c), хэш-таблица обновления h [c] = 7.
Найти новое окно, наименьшее значение - 3 (из b), а наибольшее значение - 7 (с).
Новое окно - от 3 до 7 = > 5.
Продолжайте делать это до последнего символа строки X.
Надеюсь, теперь это ясно.
Edit
Есть некоторые проблемы с поиском значения max и min из хэша.
Мы можем сохранить отсортированный список ссылок и сопоставить его с хеш-таблицей.
Всякий раз, когда какой-либо элемент из списка ссылок изменяется, он должен быть повторно отображен в хеш-таблицу.
Обе эти операции: O (1)
Общая площадь будет m + m
Edit
Вот небольшая визуализация вышеперечисленной проблемы:
Для "coobdafceeaxab" и "abc"
шаг 0:
Начальный двусвязный список = NULL
Начальная хеш-таблица = NULL
шаг 1:
Голова ↔ [с, 0] ↔ хвост
h [c] = [0, 'указатель на c node в LL']
шаг 2:
Голова ↔ [с, 0] ↔ [б, 3] ↔ хвост
h [c] = [0, 'указатель на c node в LL'], h [b] = [3, 'указатель на b node в LL'],
Шаг 3:
Голова ↔ [с, 0] ↔ [б, 3] ↔ [а, 5] ↔ хвост
h [c] = [0, 'указатель на c node в LL'], h [b] = [3, 'указатель на b node в LL'], h [a] = [5, pointer к node в LL ']
Минимальное окно = > отличие от хвоста и головы = > (5-0) +1 = > Длина: 6
Шаг 4:
Обновите запись C до индекса 7 здесь. (Удалите 'c' node из связанного списка и добавьте его в хвост)
Голова ↔ [б, 3] ↔ [а, 5] ↔ [с, 7] ↔ хвост
h [c] = [7, новый указатель на c node в LL '], h [b] = [3,' указатель на b node в LL '], h [a] = [5, указатель на node в LL '],
Минимальное окно = > отличие от хвоста и головы = > (7-3) +1 = > Длина: 5
И так далее..
Обратите внимание, что выше Обновление списка ссылок и хэш-таблицы - это O (1).
Пожалуйста, поправьте меня, если я ошибаюсь.
Резюме:
Сложность TIme: O (n) за один проход
Космическая сложность: O (k), где k - длина строки Y
Ответ 2
Здесь мое решение в С++:
int min_width(const string& x, const set<char>& y) {
vector<int> at;
for (int i = 0; i < x.length(); i++)
if (y.count(x[i]) > 0)
at.push_back(i);
int ret = x.size();
int start = 0;
map<char, int> count;
for (int end = 0; end < at.size(); end++) {
count[x[at[end]]]++;
while (count[x[at[start]]] > 1)
count[x[at[start++]]]--;
if (count.size() == y.size() && ret > at[end] - at[start] + 1)
ret = at[end] - at[start] + 1;
}
return ret;
}
Изменить. Здесь реализована идея Джека. Это такая же сложность, как у меня, но без внутреннего цикла, который вас смущает.
int min_width(const string& x, const set<char>& y) {
int ret = x.size();
map<char, int> index;
set<int> index_set;
for (int j = 0; j < x.size(); j++) {
if (y.count(x[j]) > 0) {
if (index.count(x[j]) > 0)
index_set.erase(index[x[j]]);
index_set.insert(j);
index[x[j]] = j;
if (index.size() == y.size()) {
int i = *index_set.begin();
if (ret > j-i+1)
ret = j-i+1;
}
}
}
return ret;
}
В Java он может быть хорошо реализован с помощью LinkedHashMap:
static int minWidth(String x, HashSet<Character> y) {
int ret = x.length();
Map<Character, Integer> index = new LinkedHashMap<Character, Integer>();
for (int j = 0; j < x.length(); j++) {
char ch = x.charAt(j);
if (y.contains(ch)) {
index.remove(ch);
index.put(ch, j);
if (index.size() == y.size()) {
int i = index.values().iterator().next();
if (ret > j - i + 1)
ret = j - i + 1;
}
}
}
return ret;
}
Все операции внутри цикла принимают постоянное время (при условии, что хешированные элементы расходятся правильно).
Ответ 3
Я нашел эту очень приятную версию сложности O (N) здесь http://leetcode.com/2010/11/finding-minimum-window-in-s-which.html и немного ее сократил (удалено continue в первом while, что позволило упростить условие для второго цикла while). Обратите внимание, что это решение допускает дубликаты во второй строке, в то время как многие из вышеперечисленных ответов отсутствуют.
private static String minWindow(String s, String t) {
int[] needToFind = new int[256];
int[] hasFound = new int[256];
for(int i = 0; i < t.length(); ++i) {
needToFind[t.charAt(i)]++;
}
int count = 0;
int minWindowSize = Integer.MAX_VALUE;
int start = 0, end = -1;
String window = "";
while (++end < s.length()) {
char c = s.charAt(end);
if(++hasFound[c] <= needToFind[c]) {
count++;
}
if(count < t.length()) continue;
while (hasFound[s.charAt(start)] > needToFind[s.charAt(start)]) {
hasFound[s.charAt(start++)]--;
}
if(end - start + 1 < minWindowSize) {
minWindowSize = end - start + 1;
window = s.substring(start, end + 1);
}
}
return window;
}
Ответ 4
Существует решение O (n) этой проблемы). Это очень хорошо описано в этой статье.
http://www.leetcode.com/2010/11/finding-minimum-window-in-s-which.html
Надеюсь, что это поможет.
Ответ 5
Это мое решение в С++, только для справки.
Обновление: изначально я использовал std:: set, теперь я меняю его на tr1:: unordered_map, чтобы сократить сложность до n ^ 2, в противном случае эти две реализации выглядят довольно схожими, чтобы предотвратить эту запись от слишком длинного, я перечисляю только улучшенное решение.
#include <iostream>
#include <tr1/unordered_map>
#include <string>
using namespace std;
using namespace std::tr1;
typedef tr1::unordered_map<char, int> hash_t;
// Returns min substring width in which sentence contains all chars in word
// Returns sentence length + 1 if not found
size_t get_min_width(const string &sent, const string &word) {
size_t min_size = sent.size() + 1;
hash_t char_set; // char set that word contains
for (size_t i = 0; i < word.size(); i++) {
char_set.insert(hash_t::value_type(word[i], 1));
}
for (size_t i = 0; i < sent.size() - word.size(); i++) {
hash_t s = char_set;
for (size_t j = i; j < min(j + min_size, sent.size()); j++) {
s.erase(sent[j]);
if (s.empty()) {
size_t size = j - i + 1;
if (size < min_size) min_size = size;
break;
}
}
}
return min_size;
}
int main() {
const string x = "coobdafceeaxab";
const string y = "abc";
cout << get_min_width(x, y) << "\n";
}
Ответ 6
Реализация идеи Джека.
public int smallestWindow(String str1, String str2){
if(str1==null || str2==null){
throw new IllegalArgumentException();
}
Map<String, Node> map=new HashMap<String, Node>();
Node head=null, current=null;
for(int i=0;i<str1.length();i++){
char c=str1.charAt(i);
if(head==null){
head=new Node(c);
current=head;
map.put(String.valueOf(c), head);
}
else{
current.next=new Node(c);
current.next.pre=current;
current=current.next;
map.put(String.valueOf(c), current);
}
}
Node end=current;
int min=Integer.MAX_VALUE;
int count=0;
for(int i=0;i<str2.length();i++){
char c = str2.charAt(i);
Node n=map.get(String.valueOf(c));
if(n!=null){
if(n.index==Integer.MAX_VALUE){
count++;
}
n.index=i;
if(n==head){
Node temp=head;
head=head.next;
if(head==null){//one node
return 1;
}
head.pre=null;
temp.pre=end;
end.next=temp;
temp.next=null;
end=temp;
}
else if(end!=n){
n.pre.next=n.next;
n.next.pre=n.pre;
n.pre=end;
n.next=null;
end.next=n;
end=n;
}
if(count==str1.length()){
min=Math.min(end.index-head.index+1, min);
}
}
}
System.out.println(map);
return min;
}
Ответ 7
Простое Java-решение с использованием скользящего окна. Расширение идеи NitishMD выше:
public class StringSearchDemo {
public String getSmallestSubsetOfStringContaingSearchString(String toMatch,
String inputString) {
if (inputString.isEmpty() || toMatch.isEmpty()) {
return null;
}
// List<String> results = new ArrayList<String>(); // optional you can comment this out
String smallestMatch = "";
// String largestMatch = "";
int startPointer = 0, endPointer = 1;
HashMap<Character, Integer> toMatchMap = new HashMap<Character, Integer>();
for (char c : toMatch.toCharArray()) {
if (toMatchMap.containsKey(c)) {
toMatchMap.put(c, (toMatchMap.get(c) + 1));
} else {
toMatchMap.put(c, 1);
}
}
int totalCount = getCountofMatchingString(toMatchMap, toMatch);
for (int i = 0; i < inputString.length();) {
if (!toMatchMap.containsKey(inputString.charAt(i))) {
endPointer++;
i++;
continue;
}
String currentSubString = inputString.substring(startPointer,
endPointer);
if (getCountofMatchingString(toMatchMap, currentSubString) >= totalCount) {
// results.add(currentSubString); // optional you can comment this out
if (smallestMatch.length() > currentSubString.length()) {
smallestMatch = currentSubString;
} else if (smallestMatch.isEmpty()) {
smallestMatch = currentSubString;
}
// if (largestMatch.length() < currentSubString.length()) {
// largestMatch = currentSubString;
// }
startPointer++;
} else {
endPointer++;
i++;
}
}
// System.out.println("all possible combinations = " + results); // optional, you can comment this out
// System.out.println("smallest result = " + smallestMatch);
// System.out.println("largest result = " + largestMatch);
return smallestMatch;
}
public int getCountofMatchingString(HashMap<Character, Integer> toMatchMap,
String toMatch) {
int match = 0;
HashMap<Character, Integer> localMap = new HashMap<Character, Integer>();
for (char c : toMatch.toCharArray()) {
if (toMatchMap.containsKey(c)) {
if (localMap.containsKey(c)) {
if (localMap.get(c) < toMatchMap.get(c)) {
localMap.put(c, (localMap.get(c) + 1));
match++;
}
} else {
localMap.put(c, 1);
match++;
}
}
}
return match;
}
public static void main(String[] args) {
String inputString = "zxaddbddxyy由ccbbwwaay漢字由来";
String matchCriteria = "a由";
System.out.println("input=" + matchCriteria);
System.out.println("matchCriteria=" + inputString);
String result = (new StringSearchDemo())
.getSmallestSubsetOfStringContaingSearchString(matchCriteria, inputString);
System.out.println("smallest possbile match = " + result);
}
}
