Shortest substring of a string containing all given words

题目

Print the shortest sub-string of a string containing all the given words.

Example

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

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

Note: 假定这些target words没有重复

思路

定义一个dict来存储word和相应的index, 用一个count 来记录有多少found, 如果count 等于target words个数的时候则表示全部找到了, 这个时候把dict里最小的index 找出来,用当前index减掉最小的则是符合条件的substring的长度, iterate 整个string 把最小的找到即可。

Follow up: 如果target words 有重复应该怎么做?

Swift 题解

func shortestSubString(of str: String, targetWords:[String])  -> String {  
        var dict = [String: Int]()
        for word in targetWords {
            dict[word] = -1
        }

        let words = str.components(separatedBy: " ")
        var count = 0

        var result = [String]()

        for (index, word) in words.enumerated() {
            if let lastIndex = dict[word] {
                if lastIndex == -1 {
                    count += 1
                }

                dict[word] = index


                if count == targetWords.count {
                    if let minIndex = dict.values.min() {

                        if result.isEmpty {
                            let sub = words[minIndex...index]
                            result = Array(sub)
                        }

                        if (index - minIndex + 1) < result.count {
                            let sub = words[minIndex...index]
                            result = Array(sub)
                        }
                    }
                }
            }
        }

        return result.joined(separator: " ")
    }

chenbo

编程爱好者

Singapore