New paste
Recent API Trending Blog
Guest
 
shriyanshi24jindal

Shortest Common Supersequence

shriyanshi24jindal
Mar 28th, 2026
13
0
Never
Not a member of GistPad yet? Sign Up, it unlocks many cool features!
Java 21.24 KB | None | 0 0
copy raw download clone embed print report
  1. class Solution {
  2. // idea: Find the LCS and then substract the length of LCS from sum of both strings length
  3.  
  4. /** Recursion*/
  5. public static int minSuperSeq(String s1, String s2) {
  6.  
  7. int n = s1.length();
  8. int m = s2.length();
  9.  
  10. int length = findLCS(s1, s2, n, m);
  11. return (n+m-length);
  12. }
  13.  
  14. public static int findLCS(String s1, String s2, int n, int m)
  15. {
  16. if(n == 0 || m == 0)
  17. return 0;
  18.  
  19. // choice diagram
  20. if(s1.charAt(n-1) == s2.charAt(m-1))
  21. {
  22. return 1 + findLCS(s1, s2, n-1, m-1);
  23. }
  24.  
  25. else
  26. {
  27. int choice1 = findLCS(s1, s2, n-1, m);
  28. int choice2 = findLCS(s1, s2, n, m-1);
  29. return Math.max(choice1, choice2);
  30. }
  31. }
  32.  
  33. /** Memoization*/
  34. public static int minSuperSeq(String s1, String s2) {
  35.  
  36. int n = s1.length();
  37. int m = s2.length();
  38.  
  39. int[][] t = new int[n+1][m+1];
  40. for(int i=0; i<n+1; i++)
  41. Arrays.fill(t[i], -1);
  42.  
  43. int length = findLCS(s1, s2, n, m, t);
  44. return (n+m-length);
  45. }
  46.  
  47. public static int findLCS(String s1, String s2, int n, int m, int[][] t)
  48. {
  49. if(n == 0 || m == 0)
  50. return 0;
  51.  
  52. if(t[n][m] != -1)
  53. return t[n][m];
  54.  
  55. // choice diagram
  56. if(s1.charAt(n-1) == s2.charAt(m-1))
  57. {
  58. t[n][m] = 1 + findLCS(s1, s2, n-1, m-1, t);
  59. return t[n][m];
  60. }
  61.  
  62. else
  63. {
  64. int choice1 = findLCS(s1, s2, n-1, m, t);
  65. int choice2 = findLCS(s1, s2, n, m-1, t);
  66. t[n][m] = Math.max(choice1, choice2);
  67. return t[n][m];
  68. }
  69. }
  70.  
  71. /** Top-down approach*/
  72. public static int minSuperSeq(String s1, String s2) {
  73.  
  74. int n = s1.length();
  75. int m = s2.length();
  76.  
  77. int[][] t = new int[n+1][m+1];
  78.  
  79. // base condition
  80. for(int i=0; i<n+1; i++)
  81. {
  82. for(int j=0; j<m+1; j++)
  83. {
  84. if(i == 0 || j == 0)
  85. t[i][j] = 0;
  86. }
  87. }
  88.  
  89. for(int i=1; i<n+1; i++)
  90. {
  91. for(int j=1; j<m+1; j++)
  92. {
  93. if(s1.charAt(i-1) == s2.charAt(j-1))
  94. {
  95. t[i][j] = 1 + t[i-1][j-1];
  96. }
  97. else
  98. t[i][j] = Math.max( t[i-1][j], t[i][j-1] );
  99. }
  100. }
  101.  
  102. int length = t[n][m];
  103. return (n+m-length);
  104. }
  105. }
RAW Paste Data Copied
Public Pastes
Hello
Not a member of Fast Pastebin Alternative yet?
Sign Up, it unlocks many cool features!
 
We use cookies for various purposes including analytics. By continuing to use Fast Pastebin Alternative, you agree to our use of cookies as described in the Privacy Policy.  OK, I Understand