top of page
Caută
Poza scriitoruluioanaunciuleanu

Shortest Common Supersequence in JAVA

Given two strings as input, the task is to find the length of the shortest string that has both strings as subsequences.


Input: String firstString = "AGOBGTB"; String secondString = "GBXATB"; Output: 9 Explanation: String "AGOBXAGTB" has both string "AGOBGTB" and "GBXATB" as subsequences.


Solution:


1. static int getShortestCommonSuperSequence(String firstString, String secondString) { 2. int firstLength = firstString.length(); 3. int secondLength = secondString.length(); 4. int[][] superSequences = new int[firstLength + 1][secondLength + 1]; 5. 6. for (int i = 0; i <= firstLength; i++) { 7. for (int j = 0; j <= secondLength; j++) { 8. if (i == 0) { 9. superSequences[i][j] = j; 10. } else if (j == 0) { 11. superSequences[i][j] = i; 12. } else if (firstString.charAt(i - 1) == secondString.charAt(j - 1)) { 13. superSequences[i][j] = 1 + superSequences[i - 1][j - 1]; 14. } else { 15. superSequences[i][j] = 1 + Math.min(superSequences[i - 1][j], superSequences[i][j - 1]); 16. } 17. } 18. } 19. 20. return superSequences[firstLength][secondLength]; 21. } 22.

3 afișări0 comentarii

Postări recente

Afișează-le pe toate

Weighted Job Scheduling in JAVA

You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no...

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed...

Commenti


bottom of page