Рассмотрим случай ниже:
S = eefe
^
с A = e и B = eef Вы не можете взять первое e с A, потому что результирующая подстрока будет efe и B не может соответствовать efe.
Так что в случае двусмысленности вы должны исследовать два условия: A взять или B взять?
рекурсия быть:
// return true if A and B can match S, false otherwise
bool AOrB(s, iS, iA, iB) {
if (iS > s.length) {
// we consumed all chars in S: SUCCESS
return true
}
a = A[iA]
b = B[iB]
s = S[iS]
// consider all possibilities...
if (a == s) {
if (b == s) {
// we need to explore both cases
return AOrB(s, iS+1, iA+1, iB) || AOrB(s, iS+1, iA, iB+1)
} else {
// only A is candidate!
return AOrB(s, iS+1, iA+1, iB)
}
} else {
if (b == s) {
// only B is candidate
return AOrB(s, iS+1, iA, iB+1)
} else {
// no one matches s
return false
}
}
}
Это можно упростить до
AOrB(s, iS, iA, iB) {
if (iS > s.length) {
return true
}
a = A[iA]
b = B[iB]
s = S[iS]
// consider all possibilities...
bool hasSolution = false
if (a == s) {
hasSolution ||= AOrB(s, iS+1, iA+1, iB)
}
if (b == s) {
hasSolution ||= AOrB(s, iS+1, iA, iB+1)
}
return hasSolution
}
, что эквивалентно
AOrB(s, iS, iA, iB) {
if (iS > s.length) {
return true
}
a = A[iA]
b = B[iB]
s = S[iS]
return a == s && AOrB(s, iS+1, iA+1, iB) || b == s && AOrB(s, iS+1, iA, iB+1)
}
Наконец, вы можете выбрать динамический c маршрут подхода :
- Вы строите кандидатов, начиная с
S[0] (таким образом, 0 кандидатов, если ни A, ни B не соответствуют S [0], 1, если только A или B соответствуют, или 2 кандидата, если оба совпадают) - Затем вы используете каждого из этих кандидатов в качестве отправной точки для s [1] и т. Д.
dpAOrB (S) {
// a candidate is a couple { iA, iB } where iA is the next char to be matched by A
// initially you only have one candidate: the couple { iA: 0, iB: 0 }
candidates = new Set({ iA: 0, iB: 0 })
foreach(s of S) {
nextCandidates = new Set()
foreach (candidate of candidates) {
if(A[candidate.iA] == s) {
nextCandidates.push({
iA: iA + 1, // A can take, that's a candidate
iB: candidate.iB
})
}
if(B[candidate.iB] == s) {
nextCandidates.push({
iA: iA,
iB: candidate.iB + 1
})
}
}
// if we could not generate any candidate, we can't match S
if (nextCandidates.empty () {
return false
}
candidates = nextCandidates
}
// we consumed all chars of S!
return true
}
Ниже приведена лишь небольшая демонстрация, чтобы показать, что "это работает"
function dpAOrB (S, A, B) {
let candidates = [{ iA: 0, iB: 0 }]
return S.split('').every(s => {
const nextCandidates = []
candidates.forEach(({ iA, iB }) => {
A[iA] === s && nextCandidates.push({ iA: iA + 1, iB })
B[iB] === s && nextCandidates.push({ iA, iB: iB + 1 })
})
candidates = nextCandidates
return nextCandidates.length
})
}
console.log(dpAOrB('Can we merge it? Yes, we can!', 'nwe me?s, e cn', 'Ca erg it Yewa!'))
console.log(dpAOrB("codewars", "code", "wars"))
console.log(dpAOrB("codewars", "cdwr", "oeas"))
console.log(dpAOrB("codewars", "cod", "wars"))
console.log(dpAOrB("a ttest", "a tt", "tes")) // thx Turo
Улучшение: без дублирования
Наконец, как показывает код Туро
Мы можем заметить, что у нас могут быть дубликаты кандидатов .
Рассмотрим S = 'aaaabc', A='aab', B='aac'. После употребления 'aa':
candidates [
{ iA: 2, iB: 0 },
{ iA: 1, iB: 1 },
{ iA: 1, iB: 1 },
{ iA: 0, iB: 2 }
]
Здесь мы приняли в порядке AA, AB, BA, BB. Однако AB и BA оба приводят к кандидату { iA: 1, iB: 1 }
Таким образом, мы можем уменьшить исследуемое состояние пространства, рассматривая ключ ha sh iA+''+iB и избегая дублирования.
function dpAOrB (S, A, B) {
let candidates = new Map([[0+'_'+0, { iA: 0, iB: 0 }]])
return S.split('').every(s => {
const nextCandidates = new Map()
;[...candidates].forEach(([_, { iA, iB }]) => {
A[iA] === s && nextCandidates.set([iA+1, iB].join('_'), { iA: iA + 1, iB })
B[iB] === s && nextCandidates.set([iA, iB+1].join('_'), { iA, iB: iB + 1 })
})
candidates = nextCandidates
// notice only one { iA: 1, iB: 1 }
console.log('candidates', [...candidates.values()])
return nextCandidates.size
})
}
console.log(dpAOrB("aaaa", "aab", "aac"))