alex-gru / edit-distance Public

Notifications You must be signed in to change notification settings
Fork 0
Star 0

Investigating approaches for computing Edit Distance of 2 strings

0 stars 0 forks Branches Tags Activity

Name		Name	Last commit message	Last commit date
Latest commit History 8 Commits
EditDistance.java		EditDistance.java
README.md		README.md

Repository files navigation

edit-distance

Investigating approaches for computing Edit Distance of 2 strings

brute force (exponential)
dynamic programming O(m*n) time+space
dynamic programming with optimized space complexity O(m) (wlog m < n)

Implemented during preparation for final exam on "Similarity Search VO" held by Prof. Nikolaus Augsten (Database Research Group)

Course website: https://dbresearch.uni-salzburg.at/teaching/2016ws/ssdb/

Dept. of CS, University of Salzburg, Austria