Re: [閒聊] 每日LeetCode

[ZooseWu (動物園 公告)]

※ 引述《Neuenmuller (蘇菲・諾伊恩謬拉)》之銘言：
: 1759. Count Number of Homogenous Substrings
: 找相同字元的substring 數各種substring總共出現多少次
: ex: input = "aabbbca"
: "a":   3
: "aa":  1
: "b":   3
: "bb":  2
: "bbb": 1
: "c":   1
: 總共  11
思路差不多

Intuition
每個字母都與其他字母無關

因此將整個字串根據相連的字母分成子字串計算


Approach
假設現在有一個子字串aaa

我們去計算它擁有的子字串:

index = 0: "a"
index = 1: "a", "aa"
index = 2: "a", "aa", "aaa"

從規律可以看到

第n次出現 = 新的子字串總數

所以每當長度+1我們就把答案加上長度就好

TS Code:
const mod = 1000000007
function countHomogenous (s: string): number {
  let lastChar = ""
  let subStringLength = 1
  let answer = 0
  for (let i = 0; i < s.length; i++) {
    if (s[i] === lastChar) {
      subStringLength++
    } else {
      lastChar = s[i]
      subStringLength = 1
    }
    answer = (answer + subStringLength) % mod
  }
  return answer
}

C# Code:
public class Solution
{
  public int CountHomogenous(string s)
  {
    int mod = 1000000007;
    char lastChar = '\n';
    var subStringLength = 0;
    var answer = 0;
    for (int i = 0; i < s.Length; i++)
    {
      if (s[i] == lastChar)
      {
        subStringLength++;
      }
      else
      {
        lastChar = s[i];
        subStringLength = 1;
      }
      answer = (answer + subStringLength) % mod;
    }
    return answer;
  }
}

Go Code:
func countHomogenous(s string) int {
        mod := 1000000007
        lastChar := s[0]
        subStringLength := 0
        answer := 0
        for i := 0; i < len(s); i++ {
                if s[i] == lastChar {
                        subStringLength++
                } else {
                        lastChar = s[i]
                        subStringLength = 1
                }
                answer = (answer + subStringLength) % mod
        }
        return answer
}

--
                                                                    Zoosewu
                              Yoututbe顯示PTT推文
                       可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png https://i.imgur.com/WqbLNV3.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699511328.A.580.html
推 oin1104: 大師
→ OAOb: java呢
推 SecondRun: 好像寫過這題了