New answers tagged

2

I'll list two possible approaches that might be reasonably effective in practice, though their worst-case running time is no better than what you listed. Indices You can build up an index for each word. Build a hash table. For each word that appears in any clean name, the hashtable maps that word to a list of all dirty names that contain that word. This ...


4

Heh…for the record, all I said was that the time seems to scale as approximately $\tilde O(2^{1.5n})$. If this was anything more than a conjecture based on the timing data that I included in the post, I would have said something more specific! I’m sure you’re familiar with the usual Wagner–Fischer algorithm for Levenshtein distance, where we compute $d_{i,j}...


5

This can be solved with Aho-Corasick algorithm in $O(nm + Mm)$ time, where $M$ is the number of pairs outputted. First build the Aho-Corasick automaton for the set of strings in $O(nm)$ time. Then run each string through the automaton - this takes $O(nm)$ time for running the strings through the automaton and $O(Mm)$ time for outputting the matches because ...


2

I didn't try reading the source code there, but here is one way to achieve $O(2^{3n/2})$ edit distance computations (but NOT $O^*(2^{3n/2})$ time overall). Let's define $D(a, b)$ as the Levenshtein edit distance between two strings $a$ and $b$ -- that is, the minimum number of single-character insertions, deletions or substitutions required to turn one into ...


3

The DP suggested in the comments by Yuval Filmus indeed works: we can solve the problem in $\mathcal{O}(n^{2})$ by DP. First note that we may assume that intervals are not allowed to overlap. Take any two overlapping intervals $[a, b)$ and $[c, d)$. WLOG $a \leq c$. Then we can replace the two intervals with the intervals $[a, c)$ and $[\min(b, d), \max(b, ...


0

Nice question! Here is the problem in more popular terms. Balanced Parentheses A string of parentheses is balanced if we can change it to the empty string by removing substrings "()" repeatedly. For example, empty string, "()" and "(())()((()()))" are balanced but none of "())" and ")()()(" is balanced. It is clear that a balanced string must start with ...


Top 50 recent answers are included