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.