Sunday, October 22, 2017

if string is a subsequence of another

bool (sub, s):
    if s == null || sub == null:
    if sub.length() > s.length():
        return false
    for i = 0, j = 0; i < s.length() && j < sub.length(); i++:
        if s[i] == sub[j]:
    return j == sub.length()
Follow-up: There are multiple strings to check.

Keep a ch->indexes map for s. For each ch of sub, get the first index as i which is greater than previ (i of previous ch).
(subs, s):
    subCount = 0
    cindexMap = createIndexMap(s)
    for sub in subs:
        if isSubsequence(sub, cindexMap);   
bool isSubsequence(sub, cindexMap):
    previ = -1
    for c in sub:
        if !cindexMap.hasKey(c):
            return false
        indexs = cindexMap[c]
        i = -1
        // could use binary search
        for index in indexs:
            if index > previ:
                i = index
        if i == -1:
            return false
        previ = i
    return true
map createIndexMap(s):
    // c->indexs map, indexs is list
    cindexMap = new
    for i = 0, i < t.length(), i++:
        c = t[i]
        if !cindexMap.hasKey(c):
            indexs = new list()
            cindexMap[c] = indexs
            indexs = cindexMap[c]
    return cindexMap
It's easier to check by generating all sub-sequences using combinations (uses O(2^n) space).
(subs, s):
    subCount = 0
    combinations = combine(s)
    for sub in combinations:
    for sub in subs:
        if subSet.has(sub):

// for abc, gives
// a
// ab
// abc
// ac
// b
// bc
// c
[] combine(s):
[Hat tip to LeCo]

No comments:

Post a Comment