Минимальная подстрока окна в Swift - PullRequest
Новая
       15

Минимальная подстрока окна в Swift

0 голосов
/ 26 октября 2018

Я пытаюсь быстро научиться, решая вопросы интервью. Один из вопросов, которые я пытаюсь решить, заключается в следующем.

Учитывая строку S и строку T, найдите минимальное окно в S, которое будет содержать все символы в T со сложностью O (n). 

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Моя реализация выглядит следующим образом: она содержит t строковых символов и соответствующий им индекс, полученный из s. 

func minimumWindowSubstring(_ s: String, _ t: String) -> String{

    let sChar = [Character](s)
    let tChar = [Character](t)

    var indexTemp = [[Character:Int]()]

    for tc in tChar
    {
        for (j, sc) in sChar.enumerated()
        {
            if sc == tc
            {
                indexTemp.append([tc:j])
            }
        }
    }

    return ""
}

что у меня есть в массиве indexTemp:

enter image description here

Теперь мне интересно, как я могу использовать этот массив, чтобы найти минимальное окно, я застрял.

1 Ответ

0 голосов
/ 26 октября 2018

Я подумал, что это интересная проблема, поэтому я попробовал.Вместо использования словаря я использовал простой класс для хранения диапазона найденных символов, а также String, в котором хранятся символы, которые не были найдены.

Он проходит через основную строку только один раз,так что это должно быть O (n).

Вы можете запустить это на игровой площадке.

(Я знаю, что вы нуждались в помощи в исправлении вашего кода, и мой ответ не делает этого, но яя надеюсь, что это даст вам достаточно информации, чтобы настроить свой собственный код) 

import Foundation

let string = "ADOBECODEBANC"
let sub = "ABC"

//  Create a class to hold the start and end index of the current search range, as well as a remaining variable
//  that will store which characters from sub haven't been found
class Container {
    var start: Int
    var end: Int?

    var remaining: String

    //  Consume will attempt to find a given character within our remaining string, if it has found all of them,
    //  it will store the end index
    func consume(character: Character, at index: Int) {
        //  If remaining is empty, we're done
        guard remaining != "" else { return }
        //  We're assuming that sub won't have repeating characters. If it does we'll have to chage this
        remaining = remaining.replacingOccurrences(of: String(character), with: "")
        if remaining == "" {
            end = index
        }
    }

    init(start: Int, remaining: String) {
        self.start = start
        self.remaining = remaining
    }

}

//  ClosedContainer is similar to Container, but it can only be initialized by an existing container. If the existing
//  container doesn't have an end value, the initialization will fail and return nil. This way we can weed out containers
//  for ranges where we didn't find all characters.
class ClosedContainer {
    let start: Int
    let end: Int

    init?(container: Container) {
        guard let end = container.end else { return nil }
        self.start = container.start
        self.end = end
    }

    var length: Int {
        return end - start
    }
}

var containers = [Container]()

//  Go through each character of the string
string.enumerated().forEach { index, character in
    //  Look for matches in sub
    if sub.contains(character) {
        //  Allow each existing container to attempt to consume the character
        containers.forEach { container in
            container.consume(character: character, at: index)
        }
        //  Create a new container starting on this index. It's remaining value will be the sub string without the
        //  character we just found
        let container = Container(start: index, remaining: sub.replacingOccurrences(of: String(character), with: ""))
        containers.append(container)
    }
}

//  Convert Containers into ClosedContainers using compactMap, then find the one with the shortest length
let closedContainers = containers.compactMap(ClosedContainer.init)
let maybeShortest = closedContainers.min { $0.length < $1.length }
if let shortest = maybeShortest {
    //  Convert int to String indices
    let start = string.index(string.startIndex, offsetBy: shortest.start)
    let end = string.index(string.startIndex, offsetBy: shortest.end)
    //  Get the result string
    let result = string[start...end]
    print("Shortest substring of", string, "that contains", sub, "is", result)
} else {
    //  No range was found that had all characters in sub
    print(string, "doesn't contain all characters in", sub)
}
...