Created
December 5, 2018 23:04
-
-
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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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