Longest common subsequence: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Chunes (talk | contribs)
1,827 edits
Add Factor example
Line 2,938: Line 2,938:
Swift 2.2
Swift 2.2
===Recursion===
===Recursion===
<lang Swift>func rlcs(s1:String, _ s2:String) -> String {
<lang Swift>func rlcs(_ s1: String, _ s2: String) -> String {
let x = s1.characters.count
let x = s1.characters.count
let y = s2.characters.count
let y = s2.characters.count

if x == 0 || y == 0 {
if x == 0 || y == 0 {
return ""
return ""
} else if s1[s1.startIndex.advancedBy(x - 1)] == s2[s2.startIndex.advancedBy(y - 1)] {
} else if s1[s1.index(s1.startIndex, offsetBy: x-1)] == s2[s2.index(s2.startIndex, offsetBy: y-1)] {
return rlcs(s1[s1.startIndex..<s1.startIndex.advancedBy(x - 1)],
return rlcs(String(s1[s1.startIndex..<s1.index(s1.startIndex, offsetBy: x-1)]),
s2[s2.startIndex..<s2.startIndex.advancedBy(y - 1)]) + String(s1[s1.startIndex.advancedBy(x - 1)])
String(s2[s2.startIndex..<s2.index(s2.startIndex, offsetBy: y-1)])) + String(s1[s1.index(s1.startIndex, offsetBy: x-1)])
} else {
} else {
let xstr = rlcs(s1, s2[s2.startIndex..<s2.startIndex.advancedBy(y - 1)])
let xstr = rlcs(s1, String(s2[s2.startIndex..<s2.index(s2.startIndex, offsetBy: y-1)]))
let ystr = rlcs(s1[s1.startIndex..<s1.startIndex.advancedBy(x - 1)], s2)
let ystr = rlcs(String(s1[s1.startIndex..<s1.index(s1.startIndex, offsetBy: x-1)]), s2)

return xstr.characters.count > ystr.characters.count ? xstr : ystr
return xstr.characters.count > ystr.characters.count ? xstr : ystr
}
}
}</lang>
}</lang>


===Dynamic Programming===
===Dynamic Programming===
Retrieved from "https://rosettacode.org/wiki/Longest_common_subsequence"