1.3.2 String類型常見算法

在本小節中我們將會一起學習String類型中常見的算法，學習完本小節后，相信大家不僅能對String類型常見算法有更加詳細的了解，在算法設計方面也會有一定的提高。

1. 字符串逆序輸出

字符串的逆序輸出就是將一個字符串以相反的順序進行輸出。

真實場景如下所示。

給定一個字符串'abcdefg'，執行一定的算法后，輸出的結果為'gfedcba'。

針對這個場景，以下總結出了5種不同的處理函數。

算法1

算法1的主要思想是借助數組的reverse()函數。

首先將字符串轉換為字符數組，然后通過調用數組原生的reverse()函數進行逆序，得到逆序數組后再通過調用join()函數得到逆序字符串。

通過上述的思路，我們得到下面的代碼。

---

// 算法1：借助數組的reverse()函數
function reverseString1(str) {
   return str.split('').reverse().join('');
}

---

然后通過以下的代碼進行測試。

---

var str = 'abcdefg';
console.log(reverseString1(str));

---

輸出的結果為“gfedcba”，符合預期。

算法2

算法2的主要思想是利用字符串本身的charAt()函數。

從尾部開始遍歷字符串，然后利用charAt()函數獲取字符并逐個拼接，得到最終的結果。charAt()函數接收一個索引數字，返回該索引位置對應的字符。

通過上述的思路，我們得到下面的代碼。

---

// 算法2：利用charAt()函數
function reverseString2(str) {
   var result = '';
   for(var i = str.length - 1; i >= 0; i--){
       result += str.charAt(i);
   }
   return result;
}

---

然后通過以下的代碼進行測試。

---

var str = 'abcdefg';
console.log(reverseString2(str));

---

輸出的結果為“gfedcba”，符合預期。

算法3

算法3的主要思想是通過遞歸實現逆序輸出，與算法2的處理類似。

遞歸從字符串最后一個位置索引開始，通過charAt()函數獲取一個字符，并拼接到結果字符串中，遞歸結束的條件是位置索引小于0。

通過上述的思路，我們得到下面的代碼。

---

// 算法3：遞歸實現
function reverseString3(strIn,pos,strOut){
   if(pos<0)
      return strOut;
   strOut += strIn.charAt(pos--);
   return reverseString3(strIn,pos,strOut);
}

---

然后通過以下的代碼進行測試。

---

var str = 'abcdefg';
var result = '';
console.log(reverseString3(str, str.length - 1, result));

---

輸出的結果為“gfedcba”，符合預期。

算法4

算法4的主要思想是通過call()函數來改變slice()函數的執行主體。

調用call()函數后，可以讓字符串具有數組的特性，在調用未傳入參數的slice()函數后，得到的是一個與自身相等的數組，從而可以直接調用reverse()函數，最后再通過調用join()函數，得到逆序字符串。

通過上述思路，我們得到下面的代碼。

---

// 算法4: 利用call()函數
function reverseString4(str) {
   // 改變slice()函數的執行主體，得到一個數組
   var arr = Array.prototype.slice.call(str);
   // 調用reverse()函數逆序數組
   return arr.reverse().join('');
}

---

然后通過以下的代碼進行測試。

---

var str = 'abcdefg';
console.log(reverseString4(str));

---

輸出的結果為“gfedcba”，符合預期。

算法5

算法5的主要思想是借助棧的先進后出原則。

由于JavaScript并未提供棧的實現，我們首先需要實現一個棧的數據結構，然后在棧中添加插入和彈出的函數，利用插入和彈出方法的函數字符串逆序。

首先，我們來看下基本數據結構——棧的實現。通過一個數組進行數據存儲，通過一個top變量記錄棧頂的位置，隨著數據的插入和彈出，棧頂位置動態變化。

棧的操作包括兩種，分別是出棧和入棧。出棧時，返回棧頂元素，即數組中索引值最大的元素，然后top變量減1；入棧時，往棧頂追加元素，然后top變量加1。

---

// 棧
function Stack() {
   this.data = []; // 保存棧內元素
   this.top = 0;   // 記錄棧頂位置
}
// 原型鏈增加出棧、入棧方法
Stack.prototype = {
   // 入棧:先在棧頂添加元素，然后元素個數加1
   push: function push(element) {
       this.data[this.top++] = element;
   },
   // 出棧：先返回棧頂元素，然后元素個數減1
   pop: function pop() {
       return this.data[--this.top];
   },
   // 返回棧內的元素個數，即長度
   length: function () {
       return this.top;
   }
};

---

然后通過自定義實現的棧來實現字符串的逆序輸出。

---

// 算法5：自定義棧實現
function reverseString5(str) {
   //創建一個棧的實例
   var s = new Stack();
   //將字符串轉成數組
   var arr = str.split('');
   var len = arr.length;
   var result = '';
   //將元素壓入棧內
   for(var i = 0; i < len; i++){
      s.push(arr[i]);
   }
   //輸出棧內元素
   for(var j = 0; j < len; j++){
      result += s.pop(j);
   }
   return result;
}

---

再通過以下的代碼進行測試。

---

var str = 'abcdefg';
console.log(reverseString5(str));

---

輸出的結果為“gfedcba”，符合預期。

雖然從表面上看，我們為了實現字符串逆序輸出，用很多代碼自定義實現了一個棧，這看似有點大材小用，但我們卻不能否認棧在其他方面所帶來的巨大作用。大家可以通過此實例加深對棧的理解。

2. 統計字符串中出現次數最多的字符及出現的次數

真實場景如下所示。

假如存在一個字符串'helloJavascripthellohtmlhellocss'，其中出現次數最多的字符是l，出現的次數是7次。

針對這個場景，以下總結出了5種不同的處理算法。

算法1

算法1的主要思想是通過key-value形式的對象來存儲字符串以及字符串出現的次數，然后逐個判斷出現次數最大值，同時獲取對應的字符，具體實現如下。

· 首先通過key-value形式的對象來存儲數據，key表示不重復出現的字符，value表示該字符出現的次數。

· 然后遍歷字符串的每個字符，判斷是否出現在key中。如果在，直接將對應的value值加1；如果不在，則直接新增一組key-value，value值為1。

· 得到key-value對象后，遍歷該對象，逐個比較value值的大小，找出其中最大的值并記錄key-value，即獲得最終想要的結果。

通過以上的分析，可以得到如下的代碼。

---

// 算法1
function getMaxCount(str) {
   var json = {};
   // 遍歷str的每一個字符得到key-value形式的對象
   for (var i = 0; i < str.length; i++) {
       // 判斷json中是否有當前str的值
       if (!json[str.charAt(i)]) {
           // 如果不存在，就將當前值添加到json中去
           json[str.charAt(i)] = 1;
       } else {
           // 如果存在，則讓value值加1
           json[str.charAt(i)]++;
       }
   }
   // 存儲出現次數最多的值和出現次數
   var maxCountChar = '';
   var maxCount = 0;
   // 遍歷json對象，找出出現次數最大的值
  for (var key in json) {
      // 如果當前項大于下一項
      if (json[key] > maxCount) {
          // 就讓當前值更改為出現最多次數的值
          maxCount = json[key];
          maxCountChar = key;
      }
   }
   //最終返回出現最多的值以及出現次數
   return '出現最多的值是' + maxCountChar + '，出現次數為' + maxCount;
}
var str = 'helloJavaScripthellohtmlhellocss';
getMaxCount(str); // '出現最多的值是l，出現次數為7'

---

通過上面的測試，結果符合預期。

算法2

算法2同樣會借助于key-value形式的對象來存儲字符與字符出現的次數，但是在運算上有所差別。

· 首先通過key-value形式的對象來存儲數據，key表示不重復出現的字符，value表示該字符出現的次數。

· 然后將字符串處理成數組，通過forEach()函數遍歷每個字符。在處理之前需要先判斷當前處理的字符是否已經在key-value對象中，如果已經存在則表示已經處理過相同的字符，則無須處理；如果不存在，則會處理該字符item。

· 通過split()函數傳入待處理字符，可以得到一個數組，該數組長度減1即為該字符出現的次數。

· 獲取字符出現的次數后，立即與表示出現最大次數和最大次數對應的字符變量maxCount和maxCountChar相比，如果比maxCount大，則將值寫入key-value對象中，并動態更新maxCount和maxCountChar的值，直到最后一個字符處理完成。

· 最后得到的結果即maxCount和maxCountChar兩個值。

通過以上的描述，可以得到如下的代碼。

---

// 算法2
function getMaxCount2(str) {
   var json = {};
   var maxCount = 0, maxCountChar = '';
   str.split('').forEach(function (item) {
       // 判斷json對象中是否有對應的key
       if (!json.hasOwnProperty(item)) {
           // 當前字符出現的次數
           var number = str.split(item).length - 1;
           // 直接與出現次數最大值比較，并進行更新
           if(number > maxCount) {
               // 寫入json對象
               json[item] = number;
               // 更新maxCount與maxCountChar的值
               maxCount = number;
               maxCountChar = item;
           }
       }
   });

   return '出現最多的值是' + maxCountChar + '，出現次數為' + maxCount;
}

var str = 'helloJavaScripthellohtmlhellocss';
getMaxCount2(str); // '出現最多的值是l，出現次數為7'

---

通過上面的測試，結果符合預期。

算法3

算法3的主要思想是對字符串進行排序，然后通過lastIndexOf()函數獲取索引值后，判斷索引值的大小以獲取出現的最大次數。

· 首先將字符串處理成數組，調用sort()函數進行排序，處理成字符串。

· 然后遍歷每個字符，通過調用lastIndexOf()函數，確定每個字符出現的最后位置，然后減去當前遍歷的索引，就可以確定該字符出現的次數。

· 確定字符出現的次數后，直接與次數最大值變量maxCount進行比較，如果比maxCount大，則直接更新maxCount的值，并同步更新maxCountChar的值；如果比maxCount小，則不做任何處理。

· 計算完成后，將索引值設置為字符串出現的最后位置，進行下一輪計算，直到處理完所有字符。

通過以上的描述，可以得到如下的代碼。

---

// 算法3
function getMaxCount3(str) {
   // 定義兩個變量，分別表示出現最大次數和對應的字符
   var maxCount = 0, maxCountChar = '';
   // 先處理成數組，調用sort()函數排序,再處理成字符串
   str = str.split('').sort().join('');
   for (var i = 0, j = str.length; i < j; i++) {
       var char = str[i];
       // 計算每個字符串出現的次數
       var charCount = str.lastIndexOf(char) - i + 1;
       // 與次數最大值作比較
       if (charCount > maxCount) {
           // 更新maxCount和maxCountChar的值
           maxCount = charCount;
           maxCountChar = char;
       }
       // 變更索引為字符出現的最后位置
       i = str.lastIndexOf(char);
   }
   return '出現最多的值是' + maxCountChar + '，出現次數為' + maxCount;
}

var str = 'helloJavaScripthellohtmlhellocss';
getMaxCount3(str);  // '出現最多的值是l，出現次數為7'

---

通過上面的測試，結果符合預期。

算法4

算法4的主要思想是將字符串進行排序，然后通過正則表達式將字符串進行匹配拆分，將相同字符組合在一起，最后判斷字符出現的次數。

· 首先將字符串處理成數組，調用sort()函數進行排序，處理成字符串。

· 然后設置正則表達式reg，對字符串使用match()函數進行匹配，得到一個數組，數組中的每個成員是相同的字符構成的字符串。

· 遍歷數組，依次將成員字符串長度值與maxCount值進行比較，動態更新maxCount與maxCountChar的值，直到數組所有元素處理完成。

通過以上的描述，可以得到如下的代碼。

---

// 算法4
function getMaxCount4(str) {
   // 定義兩個變量，分別表示出現最大次數和對應的字符
   var maxCount = 0, maxCountChar = '';
   // 先處理成數組，調用sort()函數排序,再處理成字符串
   str = str.split('').sort().join('');
   // 通過正則表達式將字符串處理成數組(數組每個元素為相同字符構成的字符串)
   var arr = str.match(/(\w)\1+/g);
   for (var i = 0; i < arr.length; i++) {
       // length表示字符串出現的次數
       var length = arr[i].length;
       // 與次數最大值作比較
       if (length > maxCount) {
           // 更新maxCount和maxCountChar
           maxCount = length;
           maxCountChar = arr[i][0];
       }
   }
   return '出現最多的值是' + maxCountChar + '，出現次數為' + maxCount;
}

var str = 'helloJavaScripthellohtmlhellocss';
getMaxCount4(str);  // '出現最多的值是l，出現次數為7'

---

通過上面的測試，結果符合預期。

在本算法中，使用到了正則表達式/(\w)\1+/g，其中\1表示的是(\w)匹配的內容，而\w表示的是匹配字符、數字、下畫線，(\w)\1+正則的目的是匹配重復出現的字符。

算法5

算法5的主要思想是借助replace()函數，主要實現方式如下。

· 通過while循環處理，跳出while循環的條件是字符串長度為0。

· 在while循環中，記錄原始字符串的長度originCount，用于后面做長度計算處理。

· 獲取字符串第一個字符char，通過replace()函數將char替換為空字符串''，得到一個新的字符串，它的長度remainCount相比于originCount會小，其中的差值originCount - remainCount即為該字符出現的次數。

· 確定字符出現的次數后，直接與maxCount進行比較，如果比maxCount大，則直接更新maxCount的值，并同步更新maxCountChar的值；如果比maxCount小，則不做任何處理。

· 處理至跳出while循環，得到最終結果。

通過以上的描述，可以得到如下的代碼。

---

// 算法5
function getMaxCount5(str) {
   // 定義兩個變量，分別表示出現最大次數和對應的字符
   var maxCount = 0, maxCountChar = '';
   while (str) {
       // 記錄原始字符串的長度
       var originCount = str.length;
       // 當前處理的字符
       var char = str[0];
       var reg = new RegExp(char, 'g');
       // 使用replace()函數替換處理的字符為空字符串
       str = str.replace(reg, '');
       var remainCount = str.length;
       // 當前字符出現的次數
       var charCount = originCount - remainCount;
       // 與次數最大值作比較
       if (charCount > maxCount) {
          // 更新maxCount和maxCountChar的值
          maxCount = charCount;
          maxCountChar = char;
       }
   }
   return '出現最多的值是' + maxCountChar + '，出現次數為' + maxCount;
}

var str = 'helloJavaScripthellohtmlhellocss';
getMaxCount5(str);  // '出現最多的值是l，出現次數為7'

---

通過上面的測試，結果符合預期。

3. 去除字符串中重復的字符

真實場景如下所示。

假如存在一個字符串'helloJavaScripthellohtmlhellocss'，其中存在大量的重復字符，例如h、e、l等，去除重復的字符，只保留一個，得到的結果應該是'heloJavscriptm'。

針對這個場景，以下總結出了3種不同的處理算法。

算法1

算法1的主要思想是使用key-value類型的對象存儲，key表示唯一的字符，處理完后將所有的key拼接在一起即可得到去重后的結果。

· 首先通過key-value形式的對象來存儲數據，key表示不重復出現的字符，value為boolean類型的值，為true則表示字符出現過。

· 然后遍歷字符串，判斷當前處理的字符是否在對象中，如果在，則不處理；如果不在，則將該字符添加到結果數組中。

· 處理完字符串后，得到一個數組，轉換為字符串后即可獲得最終需要的結果。

通過以上的描述，可以得到如下的代碼。

---

// 算法1
function removeDuplicateChar1(str) {
   // 結果數組
   var result = [];
   // key-value形式的對象
   var json = {};
   for (var i = 0; i < str.length; i++) {
       // 當前處理的字符
       var char = str[i];
       // 判斷是否在對象中
       if(!json[char]) {
           // value值設置為false
           json[char] = true;
           // 添加至結果數組中
           result.push(char);
       }
   }
   return result.join('');
}

var str = 'helloJavaScripthellohtmlhellocss';
removeDuplicateChar1(str);  // 'heloJavscriptm'

---

通過上面的測試，結果符合預期。

算法2

算法2的主要思想是借助數組的filter()函數，然后在filter()函數中使用indexOf()函數判斷。

· 通過call()函數改變filter()函數的執行體，讓字符串可以直接執行filter()函數。

· 在自定義的filter()函數回調中，通過indexOf()函數判斷其第一次出現的索引位置，如果與filter()函數中的index一樣，則表示第一次出現，符合條件則return出去。這就表示只有第一次出現的字符會被成功過濾出來，而其他重復出現的字符會被忽略掉。

· filter()函數返回的結果便是已經去重的字符數組，將其轉換為字符串輸出即為最終需要的結果。

通過以上的描述，可以得到如下的代碼。

---

// 算法2
function removeDuplicateChar2(str) {
   // 使用call()函數改變?lter函數的執行主體
   let result = Array.prototype.?lter.call(str, function (char, index, arr) {
      // 通過indexOf()函數與index的比較，判斷是否是第一次出現的字符
      return arr.indexOf(char) === index;
   });
   return result.join('');
}

var str = 'helloJavaScripthellohtmlhellocss';
removeDuplicateChar2(str);  // 'heloJavscriptm'

---

通過上面的測試，結果符合預期。

借助于ES6的語法，以上方法體的執行代碼還可以簡寫成一行的形式。

---

return Array.prototype.filter.call(str, (char, index, arr) => arr.indexOf 
(char) === index).join('');

---

算法3

算法3的主要思想是借助ES6中的Set數據結構，Set具有自動去重的特性，可以直接將數組元素去重。

· 將字符串處理成數組，然后作為參數傳遞給Set的構造函數，通過new運算符生成一個Set的實例。

· 將Set通過擴展運算符（...）轉換成數組形式，最終轉換成字符串獲得需要的結果。

通過以上的描述，可以得到如下的代碼。

---

// 算法3
function removeDuplicateChar3(str) {
   // 字符串轉換的數組作為參數，生成Set的實例
   let set = new Set(str.split(''));
    // 將set重新處理為數組，然后轉換成字符串
   return [...set].join('');
}

var str = 'helloJavaScripthellohtmlhellocss';
removeDuplicateChar3(str);  // 'heloJavscriptm'

---

通過上面的測試，結果符合預期。

4. 判斷一個字符串是否為回文字符串

回文字符串是指一個字符串正序和倒序是相同的，例如字符串'abcdcba'是一個回文字符串，而字符串'abcedba'則不是一個回文字符串。

需要注意的是，這里不區分字符大小寫，即a與A在判斷時是相等的。

真實的場景如下。

給定兩個字符串'abcdcba'和'abcedba'，經過一定的算法處理，分別會返回“true”和“false”。

針對這個場景，以下總結出了3種不同的處理算法。

算法1

算法1的主要思想是將字符串按從前往后順序的字符與按從后往前順序的字符逐個進行比較，如果遇到不一樣的值則直接返回“false”，否則返回“true”。

---

// 算法1
function isPalindromicStr1(str) {
   // 空字符則直接返回“true”
   if (!str.length) {
       return true;
   }
   // 統一轉換成小寫，同時轉換成數組
   str = str.toLowerCase().split('');
   var start = 0, end = str.length - 1;
   // 通過while循環判斷正序和倒序的字母
   while(start < end) {
      // 如果相等則更改比較的索引
      if(str[start] === str[end]) {
          start++;
          end--;
      } else {
          return false;
      }
   }
   return true;
}

var str1 = 'abcdcba';
var str2 = 'abcedba';

isPalindromicStr1(str1);  // true
isPalindromicStr1(str2);  // false

---

通過上面的測試，結果符合預期。

算法2

算法2與算法1的主要思想相同，將正序和倒序的字符逐個進行比較，與算法1不同的是，算法2采用遞歸的形式實現。

遞歸結束的條件有兩種情況，一個是當字符串全部處理完成，此時返回“true”；另一個是當遇到首字符與尾字符不同，此時返回“false”。而其他情況會依次進行遞歸處理。

---

// 算法2
function isPalindromicStr2(str) {
   // 字符串處理完成，則返回“true”
   if(!str.length) {
      return true;
   }
   // 字符串統一轉換成小寫
   str = str.toLowerCase();
   let end = str.length - 1;
   // 當首字符和尾字符不同，直接返回“false”
   if(str[0] !== str[end]) {
      return false;
   }
   // 刪掉字符串首尾字符，進行遞歸處理
   return isPalindromicStr2(str.slice(1, end));
}

var str1 = 'abcdcba';
var str2 = 'abcedba';

isPalindromicStr2(str1);  // true
isPalindromicStr2(str2);  // false

---

通過上面的測試，結果符合預期。

算法3

算法3的主要思想是將字符串進行逆序處理，然后與原來的字符串進行比較，如果相等則表示是回文字符串，否則不是回文字符串。

---

// 算法3
function isPalindromicStr3(str) {
   // 字符串統一轉換成小寫
   str = str.toLowerCase();
   // 將字符串轉換成數組
   var arr = str.split('');
   // 將數組逆序并轉換成字符串
    var reverseStr = arr.reverse().join('');
    return str === reverseStr;
}

var str1 = 'abcdcba';
var str2 = 'abcedba';

isPalindromicStr3(str1);  // true
isPalindromicStr3(str2);  // false

---

通過上面的測試，結果符合預期。