LeetCode: 30. Substring with Concatenation of All Words

LeetCode: 30. Substring with Concatenation of All Words

Problem: 30. Substring with Concatenation of All Words

Link: https://leetcode.com/problems/substring-with-concatenation-of-all-words/

Difficulty: Hard

Description:

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:

s = “barfoothefoobarman”,
words = [“foo”,”bar”]

Output: [0,9]

Explanation: Substrings starting at index 0 and 9 are “barfoor” and “foobar” respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:

s = “wordgoodgoodgoodbestword”,
words = [“word”,”good”,”best”,”word”]

Output: []

Solution:

Language: Swift

Runtime: 12ms
Memory: 18.5MB

Copy to Clipboard

class Solution {
    func divide(_ dividend: Int, _ divisor: Int) -> Int {
        if dividend == 0 {
            return 0
        }
        if divisor == 1 {
            return dividend
        }
        
        let isNegative = !((dividend > 0) == (divisor > 0))
        
        var dividend = abs(dividend)
        var divisor = abs(divisor)
        var result = 0
        
        while dividend >= divisor {
            var multiplier = 1
            var temp = divisor
            
            //divided by 2 as many as possible
            while dividend >= (temp << 1) {
                temp <<= 1
                multiplier <<= 1
            }
            
            //calculate the remaining number
            dividend -= temp
            result += multiplier
        }
        
        var ans = isNegative ? -result : result
        
        if ans > Int32.max {
            return Int(Int32.max)
        }
        if ans < Int32.min {
            return Int(Int32.min)
        }
        
        return ans
    }
}

Related Posts

Leave A Comment Cancel reply