JavaScript 实现查找字典序最小的字符串旋转结果

在编程领域，处理字符串问题是常见的挑战。其中，查找字典序最小的字符串旋转结果是一个有趣且具有实际应用价值的问题。本文将深入探讨如何使用 JavaScript 解决这一问题。

字典序，也称为字母序，它规定了字符之间的先后顺序。对于字符串旋转，就是将字符串的前面部分字符移到末尾，从而产生不同的排列。我们的目标是在所有这些旋转结果中找到按字典序最小的那个。

我们需要理解问题的本质。可以通过简单的示例来辅助思考，比如字符串 “abc”，它的旋转结果有 “abc”、“bca”、“cab”，其中字典序最小的是 “abc”。

在 JavaScript 中，有多种方法来实现这一功能。一种直观的方法是生成所有可能的旋转结果，然后进行比较。代码实现如下：

function findLexSmallestStringRotation(str) {
    let minStr = str;
    for (let i = 1; i < str.length; i++) {
        let rotatedStr = str.substring(i) + str.substring(0, i);
        if (rotatedStr < minStr) {
            minStr = rotatedStr;
        }
    }
    return minStr;
}

这段代码通过循环遍历所有可能的旋转位置，生成旋转后的字符串，并与当前记录的最小字典序字符串进行比较。如果新生成的字符串字典序更小，就更新最小字符串。

然而，这种方法的时间复杂度较高，为 O(n^2)，因为生成每个旋转字符串需要 O(n) 的时间，而总共需要生成 n 个旋转字符串。为了提高效率，可以采用更优化的算法。

一种优化的思路是利用双指针法。我们同时从两个位置开始比较字符串，减少不必要的比较次数。具体实现代码如下：

function findLexSmallestStringRotationOptimized(str) {
    let combined = str + str;
    let n = str.length;
    let minIndex = 0;
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (combined[minIndex + j] > combined[i + j]) {
                minIndex = i;
                break;
            } else if (combined[minIndex + j] < combined[i + j]) {
                break;
            }
        }
    }
    return str.substring(minIndex) + str.substring(0, minIndex);
}

这种方法通过将字符串拼接一次，然后利用双指针在拼接后的字符串上进行比较，时间复杂度可以降低到 O(n^2)，但实际运行效率会比第一种方法有显著提升。

通过以上方法，我们可以在 JavaScript 中高效地找到字典序最小的字符串旋转结果，为解决相关的字符串处理问题提供了有效的思路和工具。