Code Signal的stringsRearrangement

Given an array of equal-length strings, you’d like to know if it’s possible to rearrange the order of the elements in such a way that each consecutive pair of strings differ by exactly one character. Return true if it’s possible, and false if not.

Note: You’re only rearranging the order of the strings, not the order of the letters within the strings!

Example

• For inputArray = ["aba", "bbb", "bab"], the output should be
  solution(inputArray) = false.

There are 6 possible arrangements for these strings:

• ["aba", "bbb", "bab"]
• ["aba", "bab", "bbb"]
• ["bbb", "aba", "bab"]
• ["bbb", "bab", "aba"]
• ["bab", "bbb", "aba"]
• ["bab", "aba", "bbb"]
  None of these satisfy the condition of consecutive strings differing by 1 character, so the answer is false.

For inputArray = ["ab", "bb", "aa"], the output should be
solution(inputArray) = true.

It’s possible to arrange these strings in a way that each consecutive pair of strings differ by 1 character (eg: "aa", "ab", "bb" or "bb", "ab", "aa"), so return true.

Input/Output

[execution time limit] 0.5 seconds (cpp)

[memory limit] 1 GB

[input] array.string inputArray

A non-empty array of strings of lowercase letters.

Guaranteed constraints:
2 ≤ inputArray.length ≤ 10,
1 ≤ inputArray[i].length ≤ 15.

[output] boolean

Return true if the strings can be reordered in such a way that each neighbouring pair of strings differ by exactly one character (false otherwise).

思路：

这个问题可以使用图的遍历来解决。我们可以把每一个字符串看作图中的一个节点，如果两个字符串只有一个字符不同，那么它们之间就有一条边。我们的目标是找到一个字符串的排列方式，使得相邻的字符串之间都有一条边。

我们可以通过深度优先搜索(DFS)或广度优先搜索(BFS)来遍历图。以下是一种可能的解题思路：

1. 创建一个图的表示，可以使用邻接表或邻接矩阵。
2. 遍历数组中的每一对字符串，如果它们只有一个字符不同，则在图中添加一条边。
3. 选择一个起始节点，开始进行搜索。
4. 在搜索过程中，标记已经访问过的节点，避免重复访问。
5. 如果搜索过程中访问到的节点数等于数组的长度，且最后一个节点与起始节点相邻，则返回 true。
6. 如果搜索过程结束后仍未满足条件，则返回 false。

尽管这种解法可能需要遍历整个图，但由于每个字符串只与其他字符串比较一次，因此时间复杂度为 O(n^2)，其中 n 是字符串的数量。

上面的遇到相同的字符串处理不了了，失败。
std::next_permutation可以遍历组合，这个好

int diffByOneChar(string str1, string str2) {
    int diff = 0;
    
    for(int i=0;i data) {
    for(int i=1;i inputArray) {
    std::sort(inputArray.begin(), inputArray.end());
    if(check(inputArray)) return true;
    
    while (std::next_permutation(inputArray.begin(), inputArray.end())) {
        // for(int i=0;i