第二题可以这样

import java.util.*;

public class Main {
    static List<String> res;
    static Deque<String> road;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int S = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < S; i++) {
            String nums1 = sc.nextLine();
            String nums2 = sc.nextLine();
            res = new ArrayList<>();
            road = new ArrayDeque<>();
            find(nums1, "", nums2);
            printResult(res);
        }
    }

    private static void find(String origin, String now, String target) {
        if (target.equals(now)) {
            for (int i = 0; i < origin.length(); i++) {
                road.offerLast("d ");
            }
            res.add(String.join("", road));
            for (int i = 0; i < origin.length(); i++) {
                road.pollLast();
            }
            return;
        }

        if (origin == null || origin.length() == 0 || now.length() >= target.length()) {
            return;
        }

        String left = String.valueOf(origin.charAt(0));
        String remain = origin.substring(1);

        road.offerLast("d ");
        find(remain, now, target);
        road.pollLast();

        road.offerLast("l ");
        find(remain, left + now, target);
        road.pollLast();

        road.offerLast("r ");
        find(remain, now + left, target);
        road.pollLast();
    }

    private static void printResult(List<String> res) {
        System.out.println("{");
        for (String oneRes : res) {
            System.out.println(oneRes);
        }
        System.out.println("}");
    }
}