差值數(shù)組不同的字符串【LC2451】

給你一個(gè)字符串?dāng)?shù)組 words ，每一個(gè)字符串長(zhǎng)度都相同，令所有字符串的長(zhǎng)度都為 n 。

每個(gè)字符串 words[i] 可以被轉(zhuǎn)化為一個(gè)長(zhǎng)度為 n - 1 的 差值整數(shù)數(shù)組 difference[i] ，其中對(duì)于 0 <= j <= n - 2 有 difference[i][j] = words[i][j+1] - words[i][j] 。注意兩個(gè)字母的差值定義為它們?cè)谧帜副碇?位置 之差，也就是說(shuō) 'a' 的位置是 0 ，'b' 的位置是 1 ，'z' 的位置是 25 。

• 比方說(shuō)，字符串 "acb" 的差值整數(shù)數(shù)組是 [2 - 0, 1 - 2] = [2, -1] 。

words 中所有字符串 除了一個(gè)字符串以外 ，其他字符串的差值整數(shù)數(shù)組都相同。你需要找到那個(gè)不同的字符串。

請(qǐng)你返回 words中 差值整數(shù)數(shù)組 不同的字符串。

縱向比較實(shí)現(xiàn)1

• 思路

  由于words 中所有字符串 除了一個(gè)字符串以外 ，其他字符串的差值整數(shù)數(shù)組都相同。因此我們可以求出第一個(gè)字符串的差值數(shù)組，并記錄該差值數(shù)組出現(xiàn)的次數(shù)count。然后枚舉其他字符串，比較差值數(shù)組是否相同，分情況討論。

  • 如果差值數(shù)組不同，并且count>1，那么此時(shí)的字符串即為答案。
  • 但是，還存在一種情況，第一個(gè)字符串為答案，那么最終count一直為1。

• 實(shí)現(xiàn)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-466221.html

  class Solution {
      public String oddString(String[] words) {
          // 先記錄第一個(gè)字符串的差值數(shù)組，并記錄該差值數(shù)組出現(xiàn)的次數(shù)count
          // 再記錄與它不同的差值數(shù)組的下標(biāo)diff
          // 最后如果count>1，那么返回diff，否則返回0
          int n = words[0].length();
          int[] array = new int[n - 1];
          int count = 1, index = -1;
          for (int i = 0; i < n - 1; i++){
              array[i] = words[0].charAt(i + 1) - words[0].charAt(i);
          }
          for (int j = 1; j < words.length; j++){
              boolean same = true;
              for (int i = 0; i < n - 1; i++){
                  if (words[j].charAt(i + 1) - words[j].charAt(i) != array[i]){
                      same = false;
                      index = j;
                      break;
                  }
              }
              if (same) count++;
              if (count > 1 && index != -1) return words[index];
          }
          return words[0];
      }
  }
  

  • 復(fù)雜度
    • 時(shí)間復(fù)雜度：$\mathcal{O}(m?n)$，n為字符串長(zhǎng)度，m為字符串個(gè)數(shù)
    • 空間復(fù)雜度：$\mathcal{O}(n)$

縱向比較實(shí)現(xiàn)2

• 思路：

  也是先記錄第一個(gè)字符串的差值數(shù)組，然后找到與它不同的字符串，那么答案幸福二選一。再選擇另一個(gè)字符串與第一個(gè)字符串的差值數(shù)組進(jìn)行比較，如果不同，答案為第一個(gè)字符串，反之為另一個(gè)字符串

• 實(shí)現(xiàn)

  class Solution {
      public String oddString(String[] words) {
          int n = words.length;
          int i = 1;
          for(i = 1; i < n; i++){
              if(!check(words[i], words[0])){
                  break;
              }
          }
          
          for(int j = 1; j < n; j++){
              if(j != i){
                  if(check(words[j], words[0])){
                      return words[i];
                  }
                  else{
                      return words[0];
                  }
              }
          }
          return "";
      }
  
      private boolean check(String s1, String s2){
          int n = s1.length();
          int m = s1.charAt(0) - s2.charAt(0);
          for(int i = 1; i < n; i++){
              if(s1.charAt(i) - s2.charAt(i) != m){
                  return false;
              }
          }
          return true;
      }
  }
  
  作者：一只粗糙的瘋子
  鏈接：https://leetcode.cn/problems/odd-string-difference/solutions/2282834/chai-zhi-shu-zu-bu-tong-de-zi-fu-chuan-b-siph/
  來(lái)源：力扣（LeetCode）
  著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
  

到了這里，關(guān)于【每日一題Day217】LC2451差值數(shù)組不同的字符串 | 枚舉+變量記錄的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！