# LeetCode 解題筆記 (String類型題目)

解題時要注意的重點
1. 一題多解，找不同的思維；可以看討論區的解題方法
2. 不要盲目刷題，至少要帶走一些想法
3. 精通一種解法；某些題型適合某一種演算法，可以做統整
4. 定義題目內容與輸出的結果；例如考官到底要什麼；題目給的例子是不是分類過的array

[影片來源](https://www.youtube.com/watch?v=NdWYxz3izH4)

## [難度Easy] 類型：String
### 014. Longest Common Prefix
[題目網址](https://leetcode.com/problems/longest-common-prefix/)
> 給一堆字串，回傳他們共有的前贅詞(Prefix)
> Input: ["flower","flow","flight"] Output: "fl"
>

var longestCommonPrefix = function (strs) {
  if(strs.length === 0) return ''
  let same = strs[0]
  for(let i = 1; i < strs.length; i++){
    const temp = strs[i]
    let j = 0
    for(; j < same.length; j++){
      if (same[j] !== temp[j]) break
    }
    same = same.slice(0, j)
  }  
  return same
};

1. 確認給予的字串是不是只有''，是就回傳''
2. 將第一個文字整段當作前墜，開始向後跟其他文字比較
3. 當發現第J個不相同時，刪減文字，接著逐一檢查下去
4. [想法來源](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/14md.html)

var longestCommonPrefix = function (strs) {
  if(strs.length === 0) return ''
  let same = strs[0]
  let i = 1
  while(i < strs.length){    
    while(strs[i].indexOf(same)){
      same = same.substring(0, same.length - 1)      
    }
    i++
  }
  return same
};

概念同上，但是速度跟使用的資源都最優秀

### 020. Valid Parentheses
[題目網址](https://leetcode.com/problems/valid-parentheses/)
> 給一個只包含'(', ')', '{', '}', '[' , ']'這些括號字元的字串，判斷這些括號是不是合法的。 右括號必須依照正確的順序出現，"()" 與 "()[]{}" 都是合法的，但"(]" 和 "([)]"就不是。

var isValid = function (s) {
  if( s.length === 1) return false
  const obj = {
    '(': 1,
    ')': -1,
    '{': 2,
    '}': -2,
    '[': 3,
    ']': -3
  } 
  const left = ['(', '[', '{']
  const right = [')', ']', '}']
  const stack = []
  for (let i = 0; i < s.length; i++){
    if(left.indexOf(s[i]) > -1) {
      stack.push(s[i])
    } else if (right.indexOf(s[i]) > -1) { 
      const test = stack.pop()
      if(obj[s[i]] + obj[test] !== 0) return false
    }
  } 

  return stack.length === 0
};

概念上來說，(、[、{、會有一個相對應的、}、]、)，所以可以把這兩組當作抵銷的概念作處理，先從index = 0開始往後歷遍，如果遇到左側['(', '[', '{']，就存起來，遇到右側時，就拿出來比較，如果是合法的，那應該最後貯存的左側陣列stack會是0
[來源](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/20md.html)

var isValid = function (s) {
   while(s.indexOf('()') > -1 || s.indexOf('[]') > -1 || s.indexOf('{}') > -1 ){
     s = s.replace('()','').replace('[]','').replace('{}','')
   }
   return s.length === 0
};

檢查有沒有合法括號，有的話就刪除，直到沒有為止，最後檢查是否還有殘留的括號

### 038. Count and Say
[題目網址](https://leetcode.com/problems/count-and-say/)

var countAndSay = function (n) {
  let initi = '1'
  for (let i = 1; i < n; i++) { 
    let count = 1
    let string = ''
    let tempValue = initi[0]
    for (let j = 1; j <= initi.length; j++) {  
      if (tempValue === initi[j]) {
        count++
      } else if (tempValue !== initi[j]) {
        string += `${count}` + tempValue
        count = 1
        tempValue = initi[j]
      }
    }    

    initi = string    
  }
  return initi
};

1. 建立一個初始值initi = '1'，當傳入的數值n大於1時才開始閱讀數字
2. 建立一個初始的計算條件，首先要計算數字的數量，因為第一個數字已經被納入計算範圍了，所以let count = 1
3. 接著建立暫時存放累積閱讀結果的string，以及存放暫時閱讀位置的tempValue，初始值是initi[0]
4. 開始計算，因為第一個數值要跟第二個(j=1)比較，所以for-loop的停止條件為j <= initi.length (如果字串是'1'，那長度就是1，j = 1時也要進行閱讀)
5. 判斷數值是否跟下一個數值相同，是的話就數量count+1，不是的話，就停止計算，更新結果給string
6. 進行下一個數字的閱讀，直到結束為止
7. 將閱讀結果給init，繼續下一輪閱讀
8. [想法相同](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/38md.html)

P.S. 看了其他方法，好像都差不多，其他語言的解法看不懂，所以只寫一個解法
###### tags: `LeetCode` `string` `javascript`