Минимальная ширина окна в строке x, которая содержит все символы строки y

Question

Найти минимальную ширину окна в строке 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).

Answer 1

время: O (n) (один проход)
пробел: O (k)

Вот как бы я это сделал:
Создайте хеш-таблицу для всех символов из строки Y. (Я предполагаю, что все символы различны в Y).

Первый проход:
Начните с первого символа строки X.
обновить хэш-таблицу, например: для ключа 'a' введите местоположение (скажем, 1).
Продолжайте, пока не получите все символы из Y (пока все ключи в хэш-таблице не будут иметь значения).
Если вы снова получили какой-либо символ, обновите его более новое значение и удалите более старый.

Получив первый проход, возьмите наименьшее значение из хеш-таблицы и наибольшее значение.
Это минимальное окно, наблюдаемое до сих пор.

Теперь перейдите к следующему символу в строке X, обновите хеш-таблицу и посмотрите, не уменьшилось ли у вас окно.

---

Редактировать:

Давайте рассмотрим пример:
Строка x = "coobdafceeaxab"
Строка y = "abc"

Сначала инициализируйте хеш-таблицу из символов Y.
ч [а] = -1
ч [б] = -1
ч [с] = -1

Теперь, начните с первого символа X.
Первый символ c, h [c] = 0
Второй символ (o) не является частью хэша, пропустите его.
..
Четвертый символ (b), h [b] = 3
..
Шестой символ (a), введите хеш-таблицу h [a] = 5.
Теперь все ключи из хеш-таблицы имеют некоторое значение.
Наименьшее значение равно 0 (от c), а наибольшее значение равно 5 (от a), минимальное окно до сих пор составляет 6 (от 0 до 5).
Первый проход сделан.

Возьмите следующий символ. f не является частью хеш-таблицы, пропустите ее.
Следующий символ (c), обновите хеш-таблицу h [c] = 7.
Найти новое окно, наименьшее значение равно 3 (из b), а наибольшее значение равно 7 (из c).
Новое окно от 3 до 7 => 5.

Продолжайте делать это до последнего символа строки X.

Надеюсь, теперь все ясно.

---

Редактировать

Есть некоторые опасения по поводу нахождения максимального и минимального значения из хеша.
Мы можем сохранить отсортированный список ссылок и сопоставить его с хэш-таблицей.
Всякий раз, когда изменяется какой-либо элемент из списка ссылок, он должен быть повторно сопоставлен с хэш-таблицей.
Обе эти операции O (1)

Общая площадь будет м + м

---

Редактировать

Вот небольшая визуализация вышеуказанной проблемы: Для "coobdafceeaxab" и "abc"

шаг 0:
Начальный двусвязный список = NULL
Начальная хеш-таблица = NULL

шаг 1:
Голова <-> [с, 0] <-> хвост
h [c] = [0, 'указатель на узел c в LL']

шаг 2:
Голова <-> [с, 0] <-> [б, 3] <-> хвост
h [c] = [0, «указатель на узел c в LL»], h [b] = [3, «указатель на узел b в LL»],

Шаг 3:
Голова <-> [с, 0] <-> [б, 3] <-> [а, 5] <-> хвост
h [c] = [0, «указатель на узел c в LL»], h [b] = [3, «указатель на узел b в LL»], h [a] = [5, «указатель на узел в LL ']
Минимальное окно => отличие от хвоста и головы => (5-0) +1 => Длина: 6

Шаг 4:
Обновите запись C до индекса 7 здесь. (Удалить узел 'c' из связанного списка и добавить в конец)
Голова <-> [б, 3] <-> [а, 5] <-> [с, 7] <-> хвост
h [c] = [7, 'новый указатель на узел c в LL'], h [b] = [3, 'указатель на узел b в LL'], h [a] = [5, 'указатель на узел в LL '],
Минимальное окно => отличие от хвоста и головы => (7-3) +1 => Длина: 5

И так далее ..

Обратите внимание, что выше обновления связанного списка и обновления хэш-таблицы оба O (1).
Пожалуйста, поправьте меня, если я ошибаюсь ..

---

Описание:

Сложность времени: O (n) за один проход
Сложность пространства: O (k) где k - длина строки Y

Answer 2

Я нашел эту очень хорошую O (N) версию сложности времени здесь http://leetcode.com/2010/11/finding-minimum-window-in-s-which.html, и немного ее укоротил (убрал продолжить в первом while , что позволило упростить условие для второго , в то время как loop). Обратите внимание, что это решение допускает дублирование во второй строке, в то время как многие из приведенных выше ответов этого не делают.

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;
}

Answer 3

Вот мое решение на C ++:

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;
}

Все операции внутри циклазанять постоянное время (при условии, что хэшированные элементы распределены правильно).

Answer 4

Существует O (n решение этой проблемы). Это очень хорошо описано в этой статье. http://www.leetcode.com/2010/11/finding-minimum-window-in-s-which.html Надеюсь, это поможет.

Answer 5

Это мое решение на C ++, просто для справки.

Обновление : изначально я использовал 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's 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";
}

Answer 6

Простое решение 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);
}

}

Answer 7

Реализация идеи Джека.

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;
    }