Swift O(N) solution


  • 0
    S
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {
            guard words.count > 0 else {
                return []
            }
            
            let sc = NSString(string: s)
            let wlen = words.first!.characters.count
            var rt = [Int]()
            guard sc.length >= wlen*words.count else {
                return rt
            }
            
            var dict = [String : Int]()
            for word in words{
                if dict[word] != nil {
                    dict[word]! += 1
                }
                else{
                    dict[word]  = 1
                }
            }
            
            for i in 0 ..< wlen {
                var splitStrs = [String]()
                var m = 0
                while i+(m+1)*wlen <= sc.length{
                    splitStrs.append(sc.substring(with: NSMakeRange(i+m*wlen, wlen)))
                    m += 1
                }
                
                guard splitStrs.count >= words.count else {
                    break
                }
                
                var fitCount = 0
                var s = 0
                var s2 = -1
                var subDict = [String : Int]()
                for j in 0 ..< splitStrs.count {
                    let subS = splitStrs[j]
                    if dict[subS] != nil {
                        fitCount += 1
                        if subDict[subS] != nil {
                            subDict[subS]! += 1
                        }
                        else{
                            subDict[subS] = 1
                        }
                        
                        if subDict[subS]! > dict[subS]! {
                            for n in s ..< j {
                                let subS2 = splitStrs[n]
                                if subS2 == subS {
                                    s2 = n
                                    break
                                }
                            }
                        }
                        else{
                            if fitCount == words.count {
                                rt.append(i+s*wlen)
                                s2 = s
                            }
                        }
                    }
                    else{
                        s2 = j
                    }
                    
                    if s2 >= 0{
                        for k in s ... s2 {
                            let subS = splitStrs[k]
                            if subDict[subS] != nil {
                                fitCount -= 1
                                subDict[subS]! -= 1
                            }
                        }
                        
                        s = s2+1
                        s2 = -1
                    }
                }
            }
                
            return rt
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.