diff options
author | Jack Sangdahl <[email protected]> | 2025-09-17 20:45:22 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-17 20:45:22 -0600 |
commit | 0d81814bf3d0d8358d1e527de88683732ed55d23 (patch) | |
tree | 3bb0a86293810df33f02131539e8531593fa050d /plates_between_candles.py | |
parent | b07d9a7387ba1b74698af076782b27fd773a696e (diff) | |
download | leetcode-0d81814bf3d0d8358d1e527de88683732ed55d23.tar.gz leetcode-0d81814bf3d0d8358d1e527de88683732ed55d23.zip |
2055. plates between candles
Diffstat (limited to 'plates_between_candles.py')
-rw-r--r-- | plates_between_candles.py | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/plates_between_candles.py b/plates_between_candles.py new file mode 100644 index 0000000..a1eec44 --- /dev/null +++ b/plates_between_candles.py @@ -0,0 +1,36 @@ +# 2055. Plates Between Candles +import bisect + +""" +there is a long table with a line of plates and candles arranged on top of +it. you are given a 0-indexed string 's' consisting of characters '*' and '|' +only where '*' represents a plate and '|' represents a candle. return an +integer array 'answer' where 'answer[i]' is the answer to the i'th query. +""" + + +class Solution(object): + def platesBetweenCandles(self, s, queries): + """ + :type s: str + :type queries: List[List[int]] + :rtype: List[int] + """ + dp = [i for i, j in enumerate(s) if j == "|"] + ans = [] + for a, b in queries: + i = bisect.bisect_left(dp, a) + j = bisect.bisect(dp, b) - 1 + ans.append((dp[j] - dp[i]) - (j - i) if i < j else 0) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.platesBetweenCandles(s="**|**|***|", queries=[[2, 5], [5, 9]])) + print( + obj.platesBetweenCandles( + s="***|**|*****|**||**|*", + queries=[[1, 17], [4, 5], [14, 17], [5, 11], [15, 16]], + ) + ) |