Make writing a habit together! This is the sixth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

describe

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 a ‘*’ represents a plate and a ‘|’ represents a candle.

You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti…righti] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.

For example, s = “|||||*”, and a query [3, 8] denotes the substring “*||**|”. The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right. Return an integer array answer where answer[i] is the answer to the ith query.

Example 1:

Input: s = "| | | * * * * * * *", the queries = [(2, 5], [5, 9]] Output: [2, 3] Explanation: - queries[0] has two plates between candles. - queries[1] has three plates between candles.Copy the code

Example 2:

Input: s = "| | * * * * * * * * * * * * | | | | * * *", the queries = [[1], [4, 5], [14], [5, 11], [15 and 16th]] Output:,0,0,0,0 [9] Explanation: - queries[0] has nine plates between candles. - The other queries have zero plates between candles.Copy the code

Note:

  • 3 <= s.length <= 10^5
  • s consists of ‘*’ and ‘|’ characters.
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= lefti <= righti < s.length

parsing

There was a long table with a row of plates and candles. The string of a given an index of 0 s, composed of characters’ * ‘and’ | ‘, only with a ‘*’ denotes a plate, a ‘|’ on behalf of the candle. Queries [I] = [lefti, righti] represents the substring S [lefti…righti] (inclusive). For each Query, we need to find the number of plates between the candles in the substring. If, in the substring, the plate has at least one candle to the left and at least one candle to the right, the plate is considered to be between the candles.

For example, s = “| | * * | | | * * *”, substring query [3, 8] said “* | | | * *”. The number of plates between the candles in this substring is 2, because each of the two plates has at least one candle in the substring to its left and right. Return an integer array answer where answer[I] is the answer to the ith query.

After reading the question, we found that in the end, to calculate the number of valid plates in the substring, we only need to know that a plate has candles on the left and candles on the right, so we only need to prepare two lists in advance, left and right, left stands for the nearest candle position to the left of S [I]. Right denotes the nearest candle position to the right of S [I]. Then, use the prefix and the list presum to calculate the sum of all candles before the candles s[I]. Then, iterate through the queries to calculate the number of valid candles.

answer

class Solution(object):
    def platesBetweenCandles(self, s, queries):
        """
        :type s: str
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        N = len(s)
        presum = [0]*N
        left = [-1]*N
        right = [-1]*N
        
        L = -1
        for i in range(N):
            if s[i] == '|':
                L = i
            left[i] = L
            
        R = -1
        for i in range(N-1, -1, -1):
            if s[i] == '|':
                R = i
            right[i] = R
            
        t = 0    
        for i in range(N):
            if s[i] == '*':
                t += 1
            presum[i] = t
        
        result = []
        for a,b in queries:
            x = right[a]
            y = left[b]
            if x<=y and x>=a and y<=b:
                result.append(presum[y]-presum[x])
            else:
                result.append(0)
                
        return result
                
         
                
        	      
		
Copy the code

The results

Each node in the given Python online submission is linked to each node in the linked link. Memory Usage: The linked submissions in Python online submissions for Plates Between different colors.Copy the code

Original link: leetcode.com/problems/pl…

Your support is my biggest motivation