Naive Solution (Median String Problem with Unbounded Alphabets Median String Problem)
Jump to navigation
Jump to search
Time Complexity
{2}^$O(n)$
Space Complexity
$O(n)$ words
(Keep track of current string being checked, current best string, and Levenshtein distances (which can be computed recursively using O(n) space))
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1965