https://www.acmicpc.net/problem/9177
initial
I thought this was a piece of cake where we use 2 queues and if there are matching letters in the queues, we pop the letters. If both queues are empty, we have a valid case. But this does not work if the 2 words have same alphabets and thus do not explore all the possibilities. Like if we have aa,ab and we want to make abaa, this won't work.
from collections import deque
n = int(input())
for i in range(n):
a, b, c = map(str, input().split())
queue1 = deque(a)
queue2 = deque(b)
index = 0
while queue1 and queue2:
if c[index] == queue1[0]:
index += 1
queue1.popleft()
elif c[index] == queue2[0]:
index += 1
queue2.popleft()
else:
break
if queue1 and queue2:
print("Data set {}:".format(i+1), "no")
else:
print("Data set {}:".format(i+1), "yes")solution
I actually initially thought of bfs but wasn't sure how to implement so I just went on with this simple initial approach. This is not a 2x2 board matrix question, which I am used to do BFS on. Instead of putting the x,y starting position in the queue, in these kind of string questions we need to put the indexes in the queue.
I would have thought of starting with [0,0,0] but starting from the end index of each word is cleaner because we can put a condition where if all indexes reach 0 that it is True case.
A mistake I did was to mark visited[len(a)-1][len(b)-1] as True for starting BFS. I am not sure why it doesn't work if i put that.
[Revision 5 mins later] actually visited[len(a)][len(b)] doesn't cause error and it is obvious why because it doesn't affect the logic (the visited list is not 0-indexed). But why mark visited[len(a)-1][len(b)-1] as True causes error? data set 2 doesn't work
correct code:
from collections import deque
def bfs(a, b, c):
queue = deque([(len(a), len(b), len(c))])
visited = [[False for _ in range(len(b) + 1)] for _ in range(len(a) + 1)]
while queue:
ai, bi, ci = queue.popleft()
if ai == bi == ci == 0:
return True
elif ci == 0:
return False
if ai>0 and a[ai - 1] == c[ci - 1] and not visited[ai - 1][bi]:
queue.append((ai - 1, bi, ci - 1))
visited[ai - 1][bi] = True
if bi>0 and b[bi - 1] == c[ci - 1] and not visited[ai][bi - 1]:
queue.append((ai, bi - 1, ci - 1))
visited[ai][bi - 1] = True
return False
n = int(input())
for i in range(n):
a, b, c = map(str, input().split())
if bfs(a, b, c):
print("Data set %d: yes" % (i + 1))
else:
print("Data set %d: no" % (i + 1))complexity
Time Complexity: The time complexity of the code is O(N * M), where N is the number of test cases, and M is the maximum length of the strings a, b, and c.
Space Complexity: The space complexity is O(M^2) due to the creation of the visited matrix, which has dimensions (M+1) x (M+1), and the queue data structure, which can store at most M elements during the BFS traversal for each test case.
