Skip to content

Files

Latest commit

4a1ea8f · Aug 13, 2022

History

History
141 lines (106 loc) · 3.2 KB

File metadata and controls

141 lines (106 loc) · 3.2 KB

English Version

题目描述

给你一个仅由小写英文字母组成的,  下标从 0 开始的字符串 s 。返回 s 中以相同字符开头和结尾的子字符串总数。

子字符串是字符串中连续的非空字符序列。

 

示例 1:

输入:s = "abcba"
输出:7
解释:
以相同字母开头和结尾的长度为 1 的子串是:"a"、"b"、"c"、"b" 和 "a" 。
以相同字母开头和结尾的长度为 3 的子串是:"bcb" 。
以相同字母开头和结尾的长度为 5 的子串是:"abcba" 。

示例 2:

输入:s = "abacad"
输出:9
解释:
以相同字母开头和结尾的长度为 1 的子串是:"a"、"b"、"a"、"c"、"a" 和 "d" 。
以相同字母开头和结尾的长度为 3 的子串是:"aba" 和 "aca" 。
以相同字母开头和结尾的长度为 5 的子串是:"abaca" 。

示例 3:

输入:s = "a"
输出:1
解释:
只有一个,以相同字母开头和结尾的长度为 1 的子串是:"a"。

 

提示:

  • 1 <= s.length <= 105
  • s 仅包含小写英文字母。

解法

前缀和 + 计数器。

用 counter 累计以每个字符结尾的字符串的个数。

遍历字符串 s 中每个字符 c,累加以 c 字符串结尾的字符串个数。

Python3

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        counter = [0] * 26
        ans = 0
        for c in s:
            i = ord(c) - ord('a')
            counter[i] += 1
            ans += counter[i]
        return ans

Java

class Solution {
    public long numberOfSubstrings(String s) {
        int[] counter = new int[26];
        long ans = 0;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            ++counter[i];
            ans += counter[i];
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long numberOfSubstrings(string s) {
        vector<int> counter(26);
        long long ans = 0;
        for (char c : s) {
            int i = c - 'a';
            ++counter[i];
            ans += counter[i];
        }
        return ans;
    }
};

Go

func numberOfSubstrings(s string) int64 {
	var ans int64
	counter := make([]int64, 26)
	for _, c := range s {
		i := c - 'a'
		counter[i]++
		ans += counter[i]
	}
	return ans
}

...