Submission #15892946


Source Code Expand

Copy
import java.util.*;

public class Main {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		Lcs(s.toCharArray(), t.toCharArray());
	}

	public static void Lcs(char[] s, char[] t) {
		int[][] dp = new int[s.length + 1][t.length + 1];
		helper(s, t, dp, s.length, t.length);
		StringBuilder sb = new StringBuilder("");
		dfs(dp, s, t, s.length, t.length, sb);
		System.out.println(sb);
	}

	private static void dfs(int[][] dp, char[] s, char[] t, int i, int j, StringBuilder result) {
		if (i == 0 || j == 0)
			return;
		if (s[i - 1] == t[j - 1]) {
			dfs(dp, s, t, i - 1, j - 1, result);
			result.append(s[i - 1]);
			return;
		}
		if (dp[i - 1][j] == dp[i][j]) {
			dfs(dp, s, t, i - 1, j, result);
			return;
		} else {
			dfs(dp, s, t, i, j - 1, result);
			return;
		}
	}

	private static int helper(char[] s, char[] t, int[][] dp, int i, int j) {
		if (i == 0 || j == 0) {
			return 0;
		}
		if (dp[i][j] != 0) {
			return dp[i][j];
		}
		if (s[i - 1] == t[j - 1]) {
			dp[i][j] = 1 + helper(s, t, dp, i - 1, j - 1);
		} else {
			dp[i][j] = Math.max(helper(s, t, dp, i - 1, j), helper(s, t, dp, i, j - 1));
		}
		return dp[i][j];
	}
}

Submission Info

Submission Time
Task F - LCS
User nachik
Language Java (OpenJDK 11.0.6)
Score 0
Code Size 1274 Byte
Status
Exec Time 2209 ms
Memory 87448 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
× 15
× 3
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13
Case Name Status Exec Time Memory
0_00 106 ms 35368 KB
0_01 103 ms 35472 KB
0_02 100 ms 35320 KB
0_03 100 ms 35452 KB
1_00 113 ms 35500 KB
1_01 108 ms 35308 KB
1_02 158 ms 85284 KB
1_03 2209 ms 87132 KB
1_04 2209 ms 87352 KB
1_05 2209 ms 87220 KB
1_06 156 ms 85348 KB
1_07 238 ms 87040 KB
1_08 276 ms 87092 KB
1_09 273 ms 87140 KB
1_10 261 ms 87212 KB
1_11 272 ms 87180 KB
1_12 264 ms 87404 KB
1_13 258 ms 87448 KB