【leetcode】893. Groups of Special-Equivalent Strings
Algorithm
【leetcode】893. Groups of Special-Equivalent Strings
https://leetcode.com/problems/groups-of-special-equivalent-strings/
1)problem
You are given an array A
of strings.
Two strings S
and T
are special-equivalent if after any number of moves, S == T.
A move consists of choosing two indices i
and j
with i % 2 == j % 2
, and swapping S[i]
with S[j]
.
Now, a group of special-equivalent strings from A is a non-empty subset S of A
such that any string not in S is not special-equivalent with any string in S.
Return the number of groups of special-equivalent strings from A
.
Example 1:
Input: ["a","b","c","a","c","c"]
Output: 3
Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]
Example 2:
Input: ["aa","bb","ab","ba"]
Output: 4
Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]
Example 3:
Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]
Example 4:
Input: ["abcd","cdab","adcb","cbad"]
Output: 1
Explanation: 1 group ["abcd","cdab","adcb","cbad"]
Note:
1 <= A.length <= 1000
1 <= A[i].length <= 20
- All
A[i]
have the same length. - All
A[i]
consist of only lowercase letters.
2)answer
统计奇数位和偶数位的个字符出现的次数,如果 S0
串和 S1
串统计的结果相同,则它们是 special-equivalent 的。
3)solution
- 将字符串拆分为两个子字符串,1个包含偶数索引字符,1个包含奇数字符串
- 对两个子字符串进行排序(这样做是因为如果可以将字符串与另一个字符串交换,那么在排序时它们将彼此相等,因为它们必须具有相同的字符)
- 将一对字符串插入集合中,这将跟踪唯一的“组”
- 重新调整集合的大小
符合上面两个条件的是一组。
参考:https://blog.csdn.net/g_r_c/article/details/82079678
unordered_set使用方法
.find() 返回一个迭代器。这个迭代器指向和参数哈希值匹配的元素,如果没有匹配的元素,会返回这个容器的结束迭代器。
.end() 返回指向容器末尾位置的迭代器
.insert() 插入元素
视频:
https://www.youtube.com/watch?v=WJ4NtyrakT0&feature=youtu.be
图片示例:
C++实现代码:
#include "pch.h"
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>
using std::vector;
using std::string;
using std::unordered_set;
class Solution {
public:
int numSpecialEquivGroups(vector<string>& A) {
unordered_set<string> st;
for (int i = 0; i < A.size(); ++i) {
string odd = "";
string even = "";
for (int j = 0; j < A[i].size(); ++j) {
// 奇偶位的值
if (j % 2 == 0)
odd += A[i][j];
else
even += A[i][j];
}
// 排序奇偶位的值
sort(odd.begin(), odd.end());
sort(even.begin(), even.end());
st.insert(odd + even);
}
return st.size();
}
};
int main()
{
Solution solution;
vector<string> A1 = { "abcd", "cdab", "adcb", "cbad" };
vector<string> A2 = { "abc", "acb", "bac", "bca", "cab", "cba" };
int res1 = solution.numSpecialEquivGroups(A1);
int res2 = solution.numSpecialEquivGroups(A2);
}
Python实现:
def numSpecialEquivGroups(self,A):
s = set()
for w in A:
even = ''.join(sorted(w[0::2]))
odd = ''.join(sorted(w[1::2]))
s.add(odd+even)
return len(s)
最新文章
- ASP.Net请求处理机制初步探索之旅 - Part 1 前奏
- iOS 线程安全之@synchronized的用法
- 动态计算UITableViewCell高度
- [Unity3D]Unity+Android交互教程——让手机";动";起来
- folder、source folder、package 区别与联系
- 利用googleapis在日文系统中改善中文字
- Microsoft Azure 的一些限制 Global
- Codeforces Round #271 (Div. 2) F ,E, D, C, B, A
- OpenNMS界面图 .
- 【转】 设定linux 系统可用资源
- hdu 5056 Boring count
- db2 将原表列notnull属性修改为null属性的方法 (查看主键约束,唯一约束去syscat.tabconst)
- vue初级学习--环境搭建
- Mybatis-no getter for property named &#39;col_name&#39; in &#39;class com.xxx.onebean&#39;
- FM与PM信号的表现形式
- Java整理
- python中Metaclass的理解
- javascript 字符串的连接和截取
- Ubuntu下Apache虚拟主机+反向代理
- 转换es6
热门文章
- js 各种事件 如:点击事件、失去焦点、键盘事件等
- pt-kill 用法记录
- jenkins 构建
- Kafka技术内幕 读书笔记之(四) 新消费者——消费者提交偏移量
- 细说shiro之一:shiro简介
- Python Thrift 简单示例
- 【python小练】图片爬虫之BeautifulSoup4
- 父div的透明度不影响子div透明度
- 第27月第18天 epoll lt et
- spring cloud心跳检测自我保护(EMERGENCY! EUREKA MAY BE INCORRECTLY CLAIMING INSTANCES ARE UP WHEN THEY&#39;RE NOT. RENEWALS ARE LESSER THAN THRESHOLD AND HENCE THE INSTANCES ARE NOT BEING EXPIRED JUST TO BE SAFE.)