You are given a string s and a 2D string array substitutions where each substitutions[i] = [old_i, new_i] indicates that you may replace any occurrence of the non-empty substring old_i in s with new_i. You may apply each substitution any number of times.
Return the lexicographically smallest string you can obtain after applying any number of substitutions.
Input: s ="abba", substitutions =[["ab","ba"],["ba","ab"]]Output: "aabb"Explanation: We can apply the first substitution to get "bbaa", then the second to get "aabb"."aabb"is the lex smallest string possible.
Example 2:
1
2
3
Input: s ="leetcode", substitutions =[["leet","code"],["code","leet"]]Output: "codecode"Explanation: "leetcode"->"codecode"(apply first substitution), which is the smallest possible.
The substitutions can form cycles (e.g., ab <-> ba), so we need to find the lexicographically smallest string reachable by repeatedly applying any substitution. This is similar to finding the smallest string in a graph of possible transformations.
Model the substitutions as a directed graph where each node is a string, and edges represent valid substitutions.
Use BFS to explore all reachable strings from the initial string, always expanding the lexicographically smallest string first (using a min-heap/priority queue).
Track visited strings to avoid cycles and redundant work.
Return the smallest string found when the queue is empty.
import heapq
from collections import defaultdict
defapply_substitutions(s, substitutions):
subs = defaultdict(list)
for old, new in substitutions:
subs[old].append(new)
visited = set()
heap = [s]
result = s
while heap:
curr = heapq.heappop(heap)
if curr in visited:
continue visited.add(curr)
result = min(result, curr)
for old, newlist in subs.items():
pos = curr.find(old)
while pos !=-1:
for new in newlist:
next_s = curr[:pos] + new + curr[pos+len(old):]
if next_s notin visited:
heapq.heappush(heap, next_s)
pos = curr.find(old, pos+1)
return result