class Solution {
public:
int maximumNumberOfStringPairs(vector<string>& words) {
}
};
6892. 最大字符串配对数目
给你一个下标从 0 开始的数组 words ，数组中包含 互不相同 的字符串。
如果字符串 words[i] 与字符串 words[j] 满足以下条件，我们称它们可以匹配：
words[i] 等于 words[j] 的反转字符串。0 <= i < j < words.length请你返回数组 words 中的 最大 匹配数目。
注意，每个字符串最多匹配一次。
示例 1：
输入：words = ["cd","ac","dc","ca","zz"] 输出：2 解释：在此示例中，我们可以通过以下方式匹配 2 对字符串： - 我们将第 0 个字符串与第 2 个字符串匹配，因为 word[0] 的反转字符串是 "dc" 并且等于 words[2]。 - 我们将第 1 个字符串与第 3 个字符串匹配，因为 word[1] 的反转字符串是 "ca" 并且等于 words[3]。 可以证明最多匹配数目是 2 。
示例 2：
输入：words = ["ab","ba","cc"] 输出：1 解释：在此示例中，我们可以通过以下方式匹配 1 对字符串： - 我们将第 0 个字符串与第 1 个字符串匹配，因为 words[1] 的反转字符串 "ab" 与 words[0] 相等。 可以证明最多匹配数目是 1 。
示例 3：
输入：words = ["aa","ab"] 输出：0 解释：这个例子中，无法匹配任何字符串。
提示：
1 <= words.length <= 50words[i].length == 2words 包含的字符串互不相同。words[i] 只包含小写英文字母。原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.9 MB, 提交时间: 2024-01-17 07:47:22
func maximumNumberOfStringPairs(words []string) int {
ans := 0
seen := map[int]int{}
for _, word := range words {
ans += seen[int(word[1]) * 100 + int(word[0])]
seen[int(word[0]) * 100 + int(word[1])] = 1
}
return ans
}
typescript 解法, 执行用时: 72 ms, 内存消耗: 51.5 MB, 提交时间: 2024-01-17 07:47:06
function maximumNumberOfStringPairs(words: string[]): number {
const n: number = words.length;
let ans: number = 0;
for (let i: number = 0; i < n; ++i) {
for (let j: number = i + 1; j < n; ++j) {
if (words[i][0] == words[j][1] && words[i][1] == words[j][0]) {
++ans;
}
}
}
return ans;
};
javascript 解法, 执行用时: 80 ms, 内存消耗: 49.4 MB, 提交时间: 2024-01-17 07:46:22
/**
* @param {string[]} words
* @return {number}
*/
var maximumNumberOfStringPairs = function(words) {
const n = words.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
if (words[i][0] == words[j][1] && words[i][1] == words[j][0]) {
++ans;
}
}
}
return ans;
};
rust 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-09-12 15:25:20
use std::collections::HashSet;
impl Solution {
pub fn maximum_number_of_string_pairs(words: Vec<String>) -> i32 {
let mut uniq = HashSet::new();
let mut ans = 0;
for word in words.into_iter() {
let s = word.chars().rev().collect::<String>();
if uniq.contains(&s) {
ans += 1;
} else {
uniq.insert(word);
}
}
ans
}
}
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-12 15:24:31
impl Solution {
pub fn maximum_number_of_string_pairs(words: Vec<String>) -> i32 {
let mut res = 0;
let mut last: [u32;128] = [0;128];
for str in words.iter() {
let s = str.as_bytes();
if last[s[0]as usize] & (1<<s[1]-b'a') != 0 {
res += 1;
} else {
last[s[0]as usize] |= 1<<s[1]-b'a';
last[s[1]as usize] |= 1<<s[0]-b'a';
}
}
res
}
}
php 解法, 执行用时: 12 ms, 内存消耗: 18.9 MB, 提交时间: 2023-09-12 15:21:33
class Solution {
/**
* @param String[] $words
* @return Integer
*/
function maximumNumberOfStringPairs($words) {
$ans = 0;
$vis = array_fill(0, 26, array_fill(0, 26, false));
foreach ( $words as $s ) {
$x = ord($s[0]) - ord('a');
$y = ord($s[1]) - ord('a');
if ( $vis[$y][$x] ) {
$ans++;
} else {
$vis[$x][$y] = true;
}
}
return $ans;
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 42 MB, 提交时间: 2023-09-12 15:18:11
class Solution {
public int maximumNumberOfStringPairs(String[] words) {
HashSet<String> set = new HashSet<>();
int cnt = 0;
for (String s : words) {
if (set.contains(s)) {
cnt++;
set.remove(s);
} else {
String t = new StringBuilder(s).reverse().toString();
set.add(t);
}
}
return cnt;
}
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 21 MB, 提交时间: 2023-06-25 09:26:27
class Solution {
public:
int maximumNumberOfStringPairs(vector<string>& words) {
// 保存前面出现过的字符串
unordered_set<string> st;
int ans = 0;
for (auto &s : words) {
auto r = s;
reverse(r.begin(), r.end());
// 看前面是否出现过反转
if (st.count(r)) ans++;
st.insert(s);
}
return ans;
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 2.5 MB, 提交时间: 2023-06-25 09:25:44
func maximumNumberOfStringPairs(words []string) (ans int) {
vis := [26][26]bool{}
for _, s := range words {
x, y := s[0]-'a', s[1]-'a'
if vis[y][x] {
ans++
} else {
vis[x][y] = true
}
}
return
}
python3 解法, 执行用时: 40 ms, 内存消耗: 15.9 MB, 提交时间: 2023-06-25 09:25:27
class Solution:
def maximumNumberOfStringPairs(self, words: List[str]) -> int:
ans, vis = 0, set()
for s in words:
if s[::-1] in vis:
ans += 1
else:
vis.add(s)
return ans