Постановка задачи
Нам даны две текстовые строки.
Нам нужно найти длину наибольшей общей подпоследовательности.
Что такое подпоследовательность?
Вы можете думать об этом как о расположении символов в определенной последовательности.
Пример (взято из leetCode)
Text1 = «abcde» Text2 = «туз»
Визуализируйте и найдите общий символ в двух приведенных выше текстовых строках и посмотрите, расположены ли они в определенном порядке.
Вы можете видеть, что обе строки имеют общий «туз». Это подпоследовательность? Да
Потому что в Text1 — «тузы» расположены так, что между ними один символ. Это означает, что удаление b и d приведет к строке Text2.
Итак, результат вашей программы должен вернуть — длина «abc», т.е. 3
Сначала мы рассмотрим решение грубой силы. Но перед этим нужно сообщить вам, что представленное здесь решение не является рекурсивным. Поэтому, пожалуйста, обратитесь к другим материалам, чтобы узнать о рекурсивном способе решения этой проблемы.
Грубая сила
Очки для покрытия -
- Логика, когда две текстовые строки равны.
- Попробуйте уменьшить итерацию, учитывая меньший размер строки во внешнем цикле.
Что не учтено в этом алгоритме -
- проверка дубликатов не производится.
функция longestCommonSubsequence (text1, text2) {
const compareSet = новый набор()
если (текст2.длина ‹ текст1.длина){
for (пусть я = 0; я ‹ text2.length; я ++) {
for(пусть j = 0; j ‹ text1.length; j++){
если (текст2[i] === текст1[j]){
compareSet.add (текст1 [j])
}
}
}
если (compareSet.size === text2.length) {
вернуть compareSet.size
}
}
если (текст1.длина ‹ текст2.длина){
for (пусть я = 0; я ‹ text1.length; я ++) {
for(пусть j = 0; j ‹ text2.length; j++){
если (текст1[i] === текст2[j]){
compareSet.add (text2 [j])
}
}
}
если (compareSet.size === text2.length) {
вернуть compareSet.size
}
}
если (текст1.длина === текст2.длина){
пусть я = 0
в то время как (я ‹ text1.length) {
если(текст1[я] != текст2[я]){
вернуть 0
}
i = i+1
}
вернуть text1.length
}
}
Временная сложность o(n²)
Улучшенная версия
По двум указателям
функция lcsImproved (текст1, текст2) {
пусть rPointer = 0
пусть lPointer = 0
пусть равно = ложь
если (текст1.длина == текст2.длина){
в то время как (rPointer ‹ text1.length) {
если (текст1[rPointer] === текст2[rPointer]){
rPointer +=1
равен = истина
}
еще{
равенство = ложь;
rPointer +=1
}
}
вернуть (isEqual === true)? rУказатель:0
}
еще{
если (текст1.длина ‹ текст2.длина){
в то время как (lPointer ‹ text2.length) {
если (текст1[rPointer] != текст2[lPointer]){
lУказатель +=1
Равно = Ложь
}
еще{
rPointer +=1
lУказатель +=1
равен = истина
}
}
вернуть (isEqual === true)? rУказатель: 0
}
если (текст2.длина ‹ текст1.длина){
в то время как (rPointer ‹ text1.length) {
если (текст2[lPointer] != текст1[rPointer]){
rPointer +=1
Равно = Ложь
}
еще{
lУказатель +=1
rPointer +=1
равен = истина
}
}
вернуть (isEqual === true)? лУказатель: 0
}
}
}
Временная сложность — o(n)
Надеюсь, это поможет! Удачного кодирования и не стесняйтесь делиться своим решением тоже :)
