Program to check whether we can stand at least k distance away from the closest contacts in Python
-
07-10-2020 - |
Pergunta
Program to check whether we can stand at least k distance away from the closest contacts in Python
Suppose we have a string s and a number k. Now each character in the string is either dot ('.') or 'x', where dot indicates an empty space and 'x' indicates a person. We have to check whether it's possible to choose a position to stand on such that the distance between us and the closest person to us is at least k. (Here the distance between each neighbouring indices is 1).
So, if the input is like s = "x...x..", k = 2, then the output will be True, as we can stand at s[2] or s[6].
To solve this, we will follow these steps −
- pos := location of x in s, if not present, pos will be -1
- if pos is same as -1 or pos>=k, then
- return True
- last_x := pos
- dist_min := 2*k-1
- Do infinite loop, do
- next_x := location of x in s from index last_x+1 to end (if x is not present, it will be -1)
- if next_x is not same as -1, then
- if next_x-last_x-1 >= dist_min, then
- return True
- last_x := next_x
- if next_x-last_x-1 >= dist_min, then
- otherwise,
- if size of s -last_x-1 >= k, then
- return False
- if size of s -last_x-1 >= k, then
- return null
Let us see the following implementation to get better understanding −
Example
class Solution: def solve(self, s, k): pos = s.find("x") if pos==-1 or pos>=k: return True last_x = pos dist_min = 2*k-1 while True: next_x = s.find("x", last_x+1) if next_x!=-1: if next_x-last_x-1 >= dist_min: return True last_x = next_x else: if len(s)-last_x-1>=k: return True return False return None ob = Solution() print(ob.solve("x...x..", 2))
Input
"x...x..", 2
Output
True
Advertisements
Não afiliado a Tutorialspoint