Skip to content

Latest commit

 

History

History
184 lines (147 loc) · 4.67 KB

File metadata and controls

184 lines (147 loc) · 4.67 KB

English Version

题目描述

给你一个下标从 0 开始的字符串 word ,字符串只包含小写英文字母。你需要选择 一个 下标并 删除 下标处的字符,使得 word 中剩余每个字母出现 频率 相同。

如果删除一个字母后,word 中剩余所有字母的出现频率都相同,那么返回 true ,否则返回 false 。

注意:

  • 字母 x 的 频率 是这个字母在字符串中出现的次数。
  • 必须 恰好删除一个字母,不能一个字母都不删除。

 

示例 1:

输入:word = "abcc"
输出:true
解释:选择下标 3 并删除该字母,word 变成 "abc" 且每个字母出现频率都为 1 。

示例 2:

输入:word = "aazz"
输出:false
解释:我们必须删除一个字母,所以要么 "a" 的频率变为 1 且 "z" 的频率为 2 ,要么两个字母频率反过来。所以不可能让剩余所有字母出现频率相同。

 

提示:

  • 2 <= word.length <= 100
  • word 只包含小写英文字母。

解法

方法一:直接模拟

遍历字符串中的每个字符,删除该字符后,判断剩余字符串中每个字符出现的频率是否相同。如果相同,返回 true,否则遍历结束,返回 false

时间复杂度 $O(n^2)$,空间复杂度 $O(n)$。其中 $n$ 为字符串的长度。

Python3

class Solution:
    def equalFrequency(self, word: str) -> bool:
        for i in range(len(word)):
            cnt = Counter(word[:i] + word[i + 1:])
            if len(set(cnt.values())) == 1:
                return True
        return False

Java

class Solution {
    public boolean equalFrequency(String word) {
        for (int i = 0; i < word.length(); ++i) {
            int[] cnt = new int[26];
            for (int j = 0; j < word.length(); ++j) {
                if (j != i) {
                    ++cnt[word.charAt(j) - 'a'];
                }
            }
            Set<Integer> vis = new HashSet<>();
            for (int v : cnt) {
                if (v > 0) {
                    vis.add(v);
                }
            }
            if (vis.size() == 1) {
                return true;
            }
        }
        return false;
    }
}

C++

class Solution {
public:
    bool equalFrequency(string word) {
        for (int i = 0; i < word.size(); ++i) {
            int cnt[26] = {0};
            for (int j = 0; j < word.size(); ++j) {
                if (j != i) {
                    ++cnt[word[j] - 'a'];
                }
            }
            unordered_set<int> vis;
            for (int v : cnt) {
                if (v) {
                    vis.insert(v);
                }
            }
            if (vis.size() == 1) {
                return true;
            }
        }
        return false;
    }
};

Go

func equalFrequency(word string) bool {
	for i := range word {
		cnt := make([]int, 26)
		for j, c := range word {
			if j != i {
				cnt[c-'a']++
			}
		}
		vis := map[int]bool{}
		for _, v := range cnt {
			if v > 0 {
				vis[v] = true
			}
		}
		if len(vis) == 1 {
			return true
		}
	}
	return false
}

TypeScript

function equalFrequency(word: string): boolean {
    const map = new Map();
    for (const c of word) {
        map.set(c, (map.get(c) ?? 0) + 1);
    }
    const count = new Map();
    for (const v of map.values()) {
        count.set(v, (count.get(v) ?? 0) + 1);
    }
    if (count.size === 1) {
        return map.size == 1 || [...count.keys()][0] === 1;
    }
    if (count.size === 2) {
        return [...count.entries()].some(
            (v, i, arr) =>
                (v[0] === 1 || v[0] - arr[i ^ 1][0] === 1) && v[1] === 1,
        );
    }
    return false;
}

...