Question: How to find the longest common subsequence in swift?
Answer:
/*
The Longest Common Subsequence (LCS) problem is to find the longest subsequence that is common to two given sequences.
Here is a possible implementation of an LCS algorithm in Swift:
*/
func longestCommonSubsequence(firstString: String, secondString: String) -> String {
let firstChars = Array(firstString)
let secondChars = Array(secondString)
var dp = Array(repeating: Array(repeating: 0, count: secondChars.count + 1), count: firstChars.count + 1)
var result = ""
for i in 1...firstChars.count {
for j in 1...secondChars.count {
if firstChars[i-1] == secondChars[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
var i = firstChars.count
var j = secondChars.count
while i > 0 && j > 0 {
if firstChars[i-1] == secondChars[j-1] {
result = String(firstChars[i-1]) + result
i -= 1
j -= 1
} else if dp[i-1][j] > dp[i][j-1] {
i -= 1
} else {
j -= 1
}
}
return result
}
let firstString = "AGCAT"
let secondString = "GAC"
let lcs = longestCommonSubsequence(firstString: firstString, secondString: secondString)
print(lcs) // prints "GAC"
/*
The above implementation uses Dynamic Programming to solve the LCS problem. It creates a 2D array "dp" with the same number of rows as the length of the first string, and the same number of columns as the length of the second string. The array is filled with 0s initially.
The outer two for loops iterate through each character in the first and second strings, respectively. For each pair of characters, if they are equal, the value in the dp array at that position is set to the value in the top-left corner of that position + 1. If they are not equal, the value in the dp array is set to the maximum value of the position above or to the left of it.
The while loop at the end of the function retraces the steps taken to fill the dp array, starting from the bottom-right corner, and appends characters to the result string whenever a match is found.
This algorithm has a time complexity of O(nm) where n and m are the lengths of the two input strings, and a space complexity of O(nm) for creating the dp array.
*/
//END
Sign up here with your email
ConversionConversion EmoticonEmoticon