Last active
April 9, 2021 19:10
-
-
Save sebringj/001299309dd84a778be6d34b66367a44 to your computer and use it in GitHub Desktop.
My sliding window algorithm
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
const contains = (str, t) => { | |
for (const c of t) { | |
if (!str.includes(c)) { | |
return false; | |
} | |
} | |
return true; | |
} | |
const findWindows = (size, s, t) => { | |
if (t.length > s.length || s.length < size) return []; | |
const windows = []; | |
for (let i = 0; i <= s.length - size; i++) { | |
const str = s.substr(i, size); | |
if (contains(str, t)) { | |
windows.push(str); | |
} | |
} | |
return windows; | |
} | |
const findAllWindows = (source, search, maxResults) => { | |
const s = source, t = search, k = maxResults; | |
const st = s.replace(/\s/g, ''); | |
const min = t.length; | |
const max = st.length; | |
let windows = []; | |
for (let i = min; i <= max; i++) { | |
if (windows.length >= k) break; | |
const foundWindows = findWindows(i, st, t).filter(w => w.length > 0); | |
windows = windows.concat(foundWindows); | |
} | |
windows.sort((a,b) => { | |
return a.length < b.length; | |
}); | |
return windows.slice(0, k); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
jsfiddle https://jsfiddle.net/dgtq91s3/