Skip to content

Instantly share code, notes, and snippets.

@mrnkr
Created December 5, 2018 23:04
Show Gist options
  • Save mrnkr/c333ccf043d7061ddf1e5a78fbd8560f to your computer and use it in GitHub Desktop.
Save mrnkr/c333ccf043d7061ddf1e5a78fbd8560f to your computer and use it in GitHub Desktop.
Dynamic programing exercise - Recieve two arrays and check if the second one contains the first (like the longest common subsequence)
import Foundation
// Returns true iif a in contained by b :)
// This is a modification of the longest common subsequence problem
func contains(a: [String], b: [String]) -> Bool {
var res: [[Int]] = Array.init(repeating: Array.init(repeating: 0, count: b.count), count: a.count)
for i in 0...a.count - 1 {
for j in 0...b.count - 1 {
if a[i] == b[j] {
if i == 0 && j == 0 {
res[i][j] = 1
} else if i == 0 && j > 0 {
res[i][j] = 1 + res[i][j-1]
} else if i > 0 && j == 0 {
res[i][j] = 1 + res[i-1][j]
} else if i > 0 && j > 0 {
res[i][j] = 1 + max(res[i-1][j], res[i][j-1])
}
} else {
if i == 0 && j > 0 {
res[i][j] = res[i][j-1]
} else if i > 0 && j == 0 {
res[i][j] = res[i-1][j]
} else if i > 0 && j > 0 {
res[i][j] = max(res[i-1][j], res[i][j-1])
}
}
}
}
return res[a.count - 1][b.count - 1] == b.count
}
let it1 = ["Montevideo", "Piria", "Atlantis", "Punta"]
let it2 = ["Montevideo", "Solis", "Piria", "Atlantis", "Salto", "Punta", "La Paloma"]
let it3 = ["Colonia", "Salto", "La Paloma"]
contains(a: it2, b: it1)
contains(a: it2, b: it3)
contains(a: it1, b: it3)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment