JavaScript能否分割字串

---

題目要求檢查使用者輸入的字串是否可以分割。

什麼是分割字串？

字串分割是指將整個輸入文字字串中的單詞分解。單詞被分解成字典中的單詞。題目更加具體，給定一些完整的單詞字典和字串文字，我們必須檢查字串的分割結果是否與所述字典中的單詞匹配。

可以用下面的輸出視覺化題目。

Given dictionary of words :  “apple , peer , pie , please , have “

Input String : “haveapplepie”

Output :  true 

如果輸入字串可以根據使用者提到的字典單詞進行分割，則結果輸出為true，否則輸出為false。

演算法

這裡提到的演算法是使用迴圈和Javascript的include方法的暴力方法，用於查詢和檢查輸入字串是否可以分割。

步驟1：宣告一個名為checkSegmentation的函式，該函式以字串陣列作為輸入，並以字典陣列作為一些單詞集合，可以使用這些單詞來確定特定字串是否可以分割。

步驟2：從for迴圈開始，可以遍歷字串的每個字元，直到stringArray.length。

步驟3：當i = 0時，我們使用substr方法將該值儲存為第一個單詞，儲存在firstSubString變數中。

步驟4：然後我們嘗試使用include Javascript方法查詢字典中的單詞是否包含儲存在firstSubString中的值。

步驟5：如果字典包含第一個子字串，我們將第一個單詞之後開始的第二個子字串儲存在secondSubString變數中。

步驟6：如果secondSubString變數的長度為0，則它只返回已在字典中找到的第一個子字串分段字串，並返回true作為結果輸出。

步驟7：如果secondSubString已經使用include方法存在於單詞字典中，則結果輸出也返回true，表明字串可以分割。

步驟8：如果上述步驟6或7中的任何步驟都沒有發生，則主函式checkSegmentation將成為一個遞迴函式，以便針對單詞字典對secondSubString執行上述所有操作和演算法步驟。

示例

function checkSegmentation(stringArray, dictionaryArray) {

   for (let i = 1; i < stringArray.length + 1; i++) 
     {

     let firstSubString = stringArray.substr(0, i);

      if (dictionaryArray.includes(firstSubString)) {

        let secondSubString = stringArray.substr(i);

     if (secondSubString.length === 0) {

         return true;
      }

     if (dictionaryArray.includes(secondSubString)) {

         return true;
      }
     
     if (checkSegmentation(secondSubString, dictionaryArray)) {
       
        return true;

      }

     }

   }

return false;

};

const dictionaryArray =  "apple , peer , pie , please , have ";

const stringArray =  "haveapple";

console.log(checkSegmentation(stringArray,dictionaryArray));

輸出

true

以下程式碼是檢視問題陳述時可以想到的最簡單的方法，稍後我們可以將其最佳化到更好的空間和時間質量，使其更高效和高質量。

在上面的程式碼中，我們聲明瞭一個名為checkSegmentation的函式，該函式使用字串陣列和字典值來檢查字串的分割。

在這裡，我們正在迭代字串的每個元素，以便每次迭代都構造子單詞，希望使用javascript include方法在字典中找到該子單詞。

時間和空間複雜度

由於該演算法是遞迴演算法，並且每次在找不到包含在字典中的第二個子字串直到字串陣列的長度時都會呼叫遞迴函式，因此它會導致指數級的最壞情況時間複雜度O(2^n)，因為遞迴函式會導致子遞迴分支形成樹狀結構，高度為2^n，因此複雜度由此確定。

我們可以使用備忘錄法將時間複雜度提高到O(n^2)，其中備忘錄法將佔用一些記憶體來儲存已經為某些字母執行的步驟，而不是重複它們。

使用上述演算法，我們可能會多次計算相同的子字串或字元，每次迭代都向前移動並朝著字串陣列的長度移動，即使完成的子字串可能兩次或多次不存在於字典中，這也會增加遞迴子呼叫，而備忘錄法可以減少演算法的這一部分。

備忘錄法是指我們將記住已經解決的子字串。

演算法 - 使用備忘錄法

步驟1：宣告一個名為segmentString的主函式，該函式以字串陣列和單詞字典作為輸入。

步驟2：從中返回一個輔助遞迴函式，該函式接受字串陣列、單詞字典、字串的起始位置和一個用於備忘錄法的空陣列。

步驟3：在名為recursiveWordFind的輔助函式內部，我們使用基本情況：如果字串陣列等於長度，則返回true；如果備忘錄陣列的起始位置不等於undefined，則返回起始索引的記憶體。

步驟4：使用起始和結束位置標誌遍歷字串陣列，以便第一個單詞或第一個子字串是具有起始位置的陣列，而第二個子字串從start +1的索引開始用於結束標誌。

步驟5：提取起始和結束位置之間的子字串，並將其儲存在inputSubString變數中。

步驟6：一旦你在字典中找到了起始和結束位置之間的特定子字串，併為主字串陣列中剩餘的字元再次重複遞迴函式，則返回所有字串字元的記憶體引用，以便不會為已經遍歷的子字串重複相同的遞迴函式，從而節省函式的效率。

主程式碼 - 使用備忘錄法

示例

function segmentString(  stringArray , dictionaryArray )
{
   return recursiveWordFind( stringArray , dictionaryArray , 0  , []);
}



function recursiveWordFind( stringArray  ,dictionaryArray , start , memo )
{ 
   if(start===stringArray.length) return true ;

   if(memo[start]!==undefined) return memo[start];

   for(let end = start +1 ; end <= stringArray.length ; end++)
   {

     let inputSubString = stringArray.substring(start,end);

     if(dictionaryArray.includes(inputSubString) && recursiveWordFind(stringArray , dictionaryArray , end , memo))

     {
       
      return memo[start]=true;

     }

   }

   return memo[start]=false;
}

const dictionaryArray =  ["apple", "pen"];

const stringArray =  "applepenapple";

console.log(segmentString(stringArray,dictionaryArray));

輸出

true 

時間和空間複雜度

備忘錄法使用記憶體引用或記憶體容器來儲存迴圈和遞迴函式的迴圈，因此時間複雜度從指數級最壞時間降低到二次時間複雜度，即O(n^2)。

結論

這就是我們如何在邏輯上和編碼上下文中解決上述問題陳述的方法，在這種情況下，這類問題陳述可以在時間、最佳化和最佳效率方面有效增長。