Shortest substring of a string containing all given words (Follow up)

题目

Print the shortest sub-string of a string containing all the given words, previously we assume target words has no duplicates, what if it has duplicates?

Example

str = "hello dog yo abc dog yo world ting bbb yo"  
targetWords = ["yo", "dog", "bbb", "yo"]

符合条件的有 "yo world ting bbb yo" 和"yo abc dog yo world ting bbb", 最短的应该是"yo world ting bbb yo"

思路

先用一个dict 来存放target words 和相应的个数(因为有duplicates), 然后iterate str, 当dict里count 都是0 的时候则代表都找到了,这个时候我们要继续iterate, 前提是把最先找到的那个word给踢出来. 这样我们就想到用一个stack 来存放先前找到的符合条件的元素和相应的index. (这里我们用了个tuple来放)

Swift 题解

func shortestSubString(of str: String, targetWords: [String]) {  
        var count = [String: Int]() //word, and its count
        for word in targetWords {
            if let current = count[word] {
                count[word] = (current + 1)
            } else {
                count[word] = 1
            }
        }

        var stack = [(Int, String)]() //tuple: 0: index 1: word
        var j = 0

        while j < str.count {
            let word = str[j]

            if let worldCount = count[word] {
                stack.append((j, word))

                if worldCount == 0 {
                    if let firstIndex = stack.firstIndex(where: {$0.1 == word }) {
                        stack.remove(at: firstIndex)
                    }
                } else {
                    let newcount = worldCount - 1
                    count[word] = newcount
                }
            }

            let sum = count.values.reduce(0, +)
            if sum == 0 {
                let sub = str[stack.first!.0...stack.last!.0]
                print(sub)

                let first = stack.removeFirst()

                count[first.1] = 1
            }

            j += 1

        }
    }

chenbo

编程爱好者

Singapore