在JavaScript中实现一个函数，通过删除重复的字母来确定一个单词是否可以由另一个单词组成 [英] Implement a function in JavaScript to determine if a word can be formed from another word by removing repeated letters

问题描述

我正在尝试在JavaScript中实现一个名为 canBeFormed 的功能，该功能可以做到这一点:

I am trying to implement a function in JavaScript called canBeFormed that does this:

const string1 = 'hellooooolooo'
const string2 = 'hellolo'
canBeFormed(string1, string2) // true since by deleting the repeated chars 'o' and 'l' we can form the word 'hellolo'

因此，如果 string2 可以由 string1 组成，如果 string1 删除一些重复的字符，则我们返回 true

So if string2 can be formed by string1 if string1 remove some duplicate chars then we return true

对于这个问题，我似乎无法提出可行的解决方案.有人可以试一试吗?

I cannot seem to come up with a workable solution to this problem. Can someone give this a shot?

顺便说一句，有人提到可以通过dfs + backtracking解决.有人可以尝试这种方法吗?

Btw, someone mentioned that this could be solved by dfs + backtracking. Can someone give that approach a try?

为澄清起见，如果该函数可以通过删除一个或多个重复字母而从第二个字符串中组成一个单词，则返回 true .

To clarify, this function return true if it can form a word from the second string provided by removing one or more repeated letters.

因此， canBeFormed("heellolo"，"hellooooolooo")将返回 false . canBeFormed("abc"，"ac")将返回 false

So canBeFormed("heellolo", "hellooooolooo") will return false. canBeFormed("abc", "ac") will return false

推荐答案

我的理解是，仅当在第一个字符串可以通过重复(连续)重复一些字符而形成第二个字符串的情况下，该函数才应返回true在第一个.

My understanding is that the function should return true if, and only when, the first string can be formed from the second by repeating (consecutively) some characters already present in the first.

该算法可能很贪婪，不需要回溯.

The algorithm can be greedy and no backtracking is needed.

function canBeFormed(a, b) {
    let i = 0;
    for (let ch of b) {
        if (ch !== a[i]) {
            // Skip duplicate letters in a
            while (a[i] === a[i-1]) {
                if (++i >= a.length) return false;
            }
            if (ch !== a[i]) return false;
        }
        ++i;
    }
    // Remaining characters should be duplicates
    while (a[i] === a[i-1]) {
        if (++i >= a.length) return true;
    }
    return false;
}

console.log(canBeFormed("hellooooollooo","hellolo")); // true
console.log(canBeFormed("abbcc", "abc")); // true
console.log(canBeFormed("aaabbb", "aaabb")); // true
console.log(canBeFormed("helloooolloo","heellolo")); // false
console.log(canBeFormed("abc", "ac")); // false
console.log(canBeFormed("abbc", "ac")); // false
console.log(canBeFormed("ababc", "abc")); // false
console.log(canBeFormed("abbcca", "abc")); // false
console.log(canBeFormed("aab", "aaab")); // false

这篇关于在JavaScript中实现一个函数，通过删除重复的字母来确定一个单词是否可以由另一个单词组成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！