class Solution:
def finalString(self, s: str) -> str:
buf = []
for c in s:
if c == 'i':
buf = buf[::-1]
else:
buf.append(c)
return ''.join(buf)
class Solution:
def asteroidCollision(self, asteroids: list[int]) -> list[int]:
s: list[int] = []
for a in asteroids:
s.append(a)
while len(s) > 1 and s[-2] > 0 > s[-1]:
if s[-2] == -s[-1]:
s.pop()
elif s[-2] < -s[-1]:
s[-2] = s[-1]
s.pop()
return s
class Solution:
def multiply(self, num1: str, num2: str) -> str:
ZERO = '0'
if ZERO in (num1, num2):
return ZERO
def ord_(x):
return ord(x) - ord(ZERO)
def chr_(x):
return chr(x + ord(ZERO))
L1, L2 = len(num1) - 1, len(num2) - 1
result = []
carry = 0
i = 0
while (i <= L1 + L2) or carry:
j = max(0, i - L2)
while j <= min(i, L1):
n1, n2 = num1[L1 - j], num2[L2 - i + j]
carry += ord_(n1) * ord_(n2)
j += 1
result.append(chr_(carry % 10))
carry //= 10
i += 1
return ''.join(result)[::-1]
class Solution:
def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
if not matrix or not matrix[0]:
return []
result = []
t, b, l, r = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
while t <= b and l <= r:
result.extend([matrix[t][x] for x in range(l, r + 1)])
result.extend([matrix[x][r] for x in range(t + 1, b + 1)])
if t < b and l < r:
result.extend([matrix[b][x] for x in range(r - 1, l, -1)])
result.extend([matrix[x][l] for x in range(b, t, -1)])
t, b, l, r = t + 1, b - 1, l + 1, r - 1
return result
class Solution:
def findBall(self, grid: list[list[int]]) -> list[int]:
N = len(grid[0])
def drop(pos: int) -> int:
for row in grid:
adj = pos + row[pos]
if not 0 <= adj < N:
return -1
if row[pos] != row[adj]:
return -1
pos = adj
return pos
return [drop(x) for x in range(N)]
class Solution1:
def backspaceCompare(self, s: str, t: str) -> bool:
S = '#'
ss, st = [], []
for c in s:
if c != S:
ss.append(c)
elif ss:
ss.pop()
for c in t:
if c != S:
st.append(c)
elif st:
st.pop()
return ss == st
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def go_left(string, pointer, backspace):
S = '#'
while pointer >= 0 and (backspace or string[pointer] == S):
backspace += (-1) ** (string[pointer] != S)
pointer -= 1
return pointer, backspace
ps, pt = len(s) - 1, len(t) - 1 # pointer
bs, bt = 0, 0 # backspace
while True:
(ps, bs), (pt, bt) = go_left(s, ps, bs), go_left(t, pt, bt)
if not (ps >= 0 and pt >= 0 and s[ps] == t[pt]):
return ps == pt == -1
ps -= 1
pt -= 1