gpt4 book ai didi

swift - Swift 中的最小窗口子串

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:13:50 26 4
gpt4 key购买 nike

我正在尝试通过解决面试问题来快速学习。我试图解决的问题之一如下。

给定一个字符串 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

现在我想知道如何使用这个数组来找到最小窗口,我卡住了。

最佳答案

我认为这是一个有趣的问题,所以我试了一下。我没有使用字典,而是使用了一个简单的类来存储找到的字符范围,以及一个 String 来存储未找到的字符。

它只经过主字符串一次,所以它应该是 O(n)。

您可以在 Playground 上运行它。

(我知道您需要帮助来修复您的代码,而我的回答并没有这样做,但我希望它能为您提供足够的洞察力来调整您自己的代码)

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

关于swift - Swift 中的最小窗口子串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53010737/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com