SWIFT: Find Longest subsequence matching a substring - Swift solution
func longestSubsequence(x: String, y: String) -> Int {
let result = x.longestCommonSubsequence(y)
return result.count
}
longestSubsequence(x: "abcd", y: "abdc") // prints 3 as abd is longest
extension String {
public func longestCommonSubsequence(_ other: String) -> String {
func lcsLength(_ other: String) -> [[Int]] {
var matrix = [[Int]](repeating: [Int](repeating: 0, count: other.count+1), count: self.count+1)
for (i, selfChar) in self.enumerated() {
for (j, otherChar) in other.enumerated() {
if otherChar == selfChar {
// Common char found, add 1 to highest lcs found so far.
matrix[i+1][j+1] = matrix[i][j] + 1
} else {
// Not a match, propagates highest lcs length found so far.
matrix[i+1][j+1] = max(matrix[i][j+1], matrix[i+1][j])
}
}
}
return matrix
}
func backtrack(_ matrix: [[Int]]) -> String {
var i = self.count
var j = other.count
var charInSequence = self.endIndex
var lcs = String()
while i >= 1 && j >= 1 {
// Indicates propagation without change: no new char was added to lcs.
if matrix[i][j] == matrix[i][j - 1] {
j -= 1
}
// Indicates propagation without change: no new char was added to lcs.
else if matrix[i][j] == matrix[i - 1][j] {
i -= 1
charInSequence = self.index(before: charInSequence)
}
// Value on the left and above are different than current cell.
// This means 1 was added to lcs length.
else {
i -= 1
j -= 1
charInSequence = self.index(before: charInSequence)
lcs.append(self[charInSequence])
}
}
return String(lcs.reversed())
}
return backtrack(lcsLength(other))
}
}
 |
| Longest subsequence matching a substring |
Sign up here with your email
ConversionConversion EmoticonEmoticon