检查是否可以以每对连续字符串相差 1 个字符的方式排列字符串

Question

给定一个等长字符串数组，您想知道是否可以重新排列元素的顺序，以使每一对连续的字符串仅相差一个字符。如果可能，则返回

true

，如果不可能，则返回

false

。

注意：您只是重新排列字符串的顺序，而不是字符串中字母的顺序！

示例

• 对于

  inputArray = ["aba", "bbb", "bab"]

  ，输出应该是：

  解决方案（inputArray）= false。

这些字符串有 6 种可能的排列方式：

   * ["aba", "bbb", "bab"]
   * ["aba", "bab", "bbb"]
   * ["bbb", "aba", "bab"]
   * ["bbb", "bab", "aba"]
   * ["bab", "bbb", "aba"]
   * ["bab", "aba", "bbb"]

这些都不满足连续字符串相差 1 个字符的条件，所以答案为 false。

• 对于

  inputArray = ["ab", "bb", "aa"]

  ，输出应该是：

  解决方案（inputArray）= true。

可以按照每对连续字符串相差 1 个字符的方式排列这些字符串（例如：

"aa", "ab", "bb"

或

"bb", "ab", "aa"

），因此返回 true。

Answer 1

我认为算法可以描述如下

1. 编写一个计算两个字符串之间差异的函数(

   difCount()

   )

2. 比较每对字符串（即 1 与 2、1 与 3、2 与 3）以检查所有字符串是否都有一个仅相差 1 个字符的“朋友”。

3. 如果至少有一个字符串没有一对，则测试失败。

arr =  ["ff", "gf", "af", "ar", "hf"];

// count how many letters are differnt between two strings
function difCount(str1, str2){
  dif_count = 0;
  [...str1].map((val, ind) => {
     // val != str2[ind] is comparison between the chars in the neighboring strings at the same indexes (i.e. first with first, second with second)
     // if comparison passes, then it is 1, so dif_count (which counts the differences) increments, otherwise it doesn't increment
     dif_count += val != str2[ind];
  })
  return dif_count;
}

// create array of zeros with the length of arr.length
checks = Array(arr.length).fill(0);

// below we compare each element with every another element.
//If there's a pair of strings str1 and str2 with the difference of 1 character, we set the corresponding indexes in "checks" array to 1.
//If the "checks" array contains all 1's then all the strings have pairs, otherwise test fails.
//If array contains duplicates, then test fails

dupes = 0;

arr.map((str1, ind1) => {
  arr.map((str2, ind2) => {
     if(difCount(str1, str2) == 1){
        checks[ind1] = 1;
        checks[ind2] = 1;
     }
     if(str1 == str2 && ind1 != ind2) dupes = 1;
  }) 
})

// So, if there're no dupes and no zeros in the checks array, then the test has passed

pass = !dupes && !checks.includes(0) ? "pass" : "fail";

console.log(pass)

Answer 2

function solution(inputArray) {
    var possible = false;

    // helper function to check permutations of the input array
    var permute = function (arr, m = []) {
        if (arr.length === 0) {
            // iterate through all permutations and check for a single character difference
            for (var i = 0; i < m.length - 1; i++) {
                var diff = 0;
                for (var j = 0; j < m[i].length; j++) {
                    if (m[i][j] !== m[i + 1][j]) {
                        diff++;
                    }
                }
                // if more than one character difference, return
                if (diff !== 1) {
                    return;
                }
            }
            possible = true;
        } else {
            for (var i = 0; i < arr.length; i++) {
                var curr = arr.slice();
                var next = curr.splice(i, 1);
                permute(curr.slice(), m.concat(next));
            }
        }
    };
    // call permute function to check all permutations
    permute(inputArray);
    return possible;
}

Answer 3

只要遵循描述中的逻辑，可能会更容易理解问题。因此，该解决方案只需三个步骤即可实现： 1. 找出 inputArray 的所有排列； 2. 生成一个函数，可以统计任意两个连续字符串之间不同字母的数量； 3. 检查重新排列的数组中的每一行。

function solution(inputArray) {
    // Generate all permutations of the input array
    const rearrangedArrs = permute(inputArray);
    
    // Compare consecutive strings in each row 
    for (let row = 0; row < rearrangedArrs.length; row++) {
        let foundBreak = true;
        for (let col = 0; col < rearrangedArrs[0].length-1; col++) {
            // Find the difference between consecutive strings 
            const charDiff = findDiff(rearrangedArrs[row][col], rearrangedArrs[row][col+1]);
            if(charDiff.length !== 1) {
               foundBreak = false;
               break;
            }
        }
        if(foundBreak === true) return true;
    }   // end outer loop
    return false;
}

// A helper function that counts how many letters are different
// between two strings
function findDiff(str1, str2) {
    let diff = '';
    str2.split('').forEach((val, idx) => {
        if(val != str1.charAt(idx)) diff += val;
    })
    return diff;
}

// A function that generates all permutations of an array of strings
function permute(strings) {
    let result = [];
    // base case
    if (strings.length === 0) return [];
    if (strings.length === 1) return [strings];
    
    // For each element in the input array, create a new 
    // array with the remaining elements and generate all
    // permutations of that array recursively
    for (let i = 0; i < strings.length; i++) {
        const currentStr = strings[i];
        const remainingStrs = strings.slice(0, i).concat(strings.slice(i + 1));
        const remainingStrsPermuted = permute(remainingStrs);
        
        // For each permutation of the remaining strings, 
        // add the current string to the beginning and create
        // a new array
        for (let j = 0; j < remainingStrsPermuted.length; j++) {
            const permutedArray =  [currentStr].concat(remainingStrsPermuted[j]);
            
            result.push(permutedArray);
        }
     }  // end outer loop
    
    return result;
}

如果您想了解更多关于如何查找两个任意字符串之间的差异，请阅读以下文章：https://en.wikipedia.org/wiki/Levenshtein_distance

Answer 4

创建一个图，每对有效字符串之间都有一条边，然后找出所形成的图中是否存在哈密尔顿路径。