JavaScript程式查詢字典序最小的字串旋轉

我們將使用 JavaScript 查詢字典序最小的字串旋轉。該方法涉及將原始字串與其自身連線起來，然後使用內建的“sort”函式按升序對連線後的字串進行排序。最後，我們將返回排序後的連線字串中最小的子字串，該子字串與原始字串具有相同的長度。這將是字典序最小的字串旋轉。

我們將透過利用 JavaScript 中可用的字串操作技術和內建函式來實現此邏輯。我們的實現結果將是一個字串，表示輸入字串的字典序最小的旋轉。這將有助於以有效的方式比較和排序字串。

將來，我們將繼續改進演算法，使其更快、更高效地查詢字典序最小的字串旋轉。

方法

以下是查詢字典序最小的字串旋轉的方法的 5 行說明：

  • 將原始字串與其自身連線起來，以確保考慮所有可能的旋轉。

  • 找到第一個不等於其下一個字元的字元，這將是最小旋轉的起始點。

  • 如果找不到此類字元，則返回原始字串，因為它已經是最小旋轉。

  • 返回連線字串的子字串，該子字串從找到的字元開始到字串末尾，作為最小旋轉。

  • 結果子字串將是字典序最小的字串旋轉。

示例

可以透過將原始字串與其自身連線起來並找到以原始字串的第一個字元開頭的最小子字串來找到字典序最小的字串旋轉。

以下是 JavaScript 中此實現的示例：

function findLexicographicallyMinimumStringRotation(str) {
   let strDouble = str + str;
   let len = str.length;
   let minRotation = strDouble.substring(0, len);
   for (let i = 1; i < len; i++) {
      let currRotation = strDouble.substring(i, i + len);
      if (currRotation < minRotation) {
         minRotation = currRotation;
      }
   }
   return minRotation;
}
const str = 'eadbc';
console.log(findLexicographicallyMinimumStringRotation(str));

解釋

  • 首先，我們將原始字串與其自身連線起來以獲得 **strDouble**。

  • 我們還定義一個變數 **len** 來儲存原始字串的長度。

  • 然後，我們使用 **strDouble**. **substring(0, len)** 初始化 **minRotation**，它是來自 **strDouble** 的長度為 **len** 的第一個子字串。這是我們查詢字典序最小的字串旋轉的起點。

  • 然後，我們使用 for 迴圈遍歷 **strDouble** 中長度為 **len** 的所有可能的子字串，從第二個字元開始。

  • 對於每次迭代，我們透過從 **strDouble** 獲取長度為 **len** 的子字串來找到當前旋轉 **currRotation**，該子字串從當前位置 **i** 開始。

  • 如果 **currRotation** 小於 **minRotation**，我們使用當前旋轉更新 **minRotation**。

  • 最後，在 for 迴圈結束後，我們返回 **minRotation** 的值，它是字典序最小的字串旋轉。

更新於： 2023年3月15日

419 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告