LeetCode 1061. Lexicographically Smallest Equivalent String
原题链接在这里:https://leetcode.com/problems/lexicographically-smallest-equivalent-string/
题目:
Given strings A
and B
of the same length, we say A[i] and B[i] are equivalent characters. For example, if A = "abc"
and B = "cde"
, then we have 'a' == 'c', 'b' == 'd', 'c' == 'e'
.
Equivalent characters follow the usual rules of any equivalence relation:
- Reflexivity: 'a' == 'a'
- Symmetry: 'a' == 'b' implies 'b' == 'a'
- Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'
For example, given the equivalency information from A
and B
above, S = "eed"
, "acd"
, and "aab"
are equivalent strings, and "aab"
is the lexicographically smallest equivalent string of S
.
Return the lexicographically smallest equivalent string of S
by using the equivalency information from A
and B
.
Example 1:
Input: A = "parker", B = "morris", S = "parser"
Output: "makkek"
Explanation: Based on the equivalency information inA
andB
, we can group their characters as[m,p]
,[a,o]
,[k,r,s]
,[e,i]
. The characters in each group are equivalent and sorted in lexicographical order. So the answer is"makkek"
.
Example 2:
Input: A = "hello", B = "world", S = "hold"
Output: "hdld"
Explanation: Based on the equivalency information inA
andB
, we can group their characters as[h,w]
,[d,e,o]
,[l,r]
. So only the second letter'o'
inS
is changed to'd'
, the answer is"hdld"
.
Example 3:
Input: A = "leetcode", B = "programs", S = "sourcecode"
Output: "aauaaaaada"
Explanation: We group the equivalent characters inA
andB
as[a,o,e,r,s,c]
,[l,p]
,[g,t]
and[d,m]
, thus all letters inS
except'u'
and'd'
are transformed to'a'
, the answer is"aauaaaaada"
.
Note:
- String
A
,B
andS
consist of only lowercase English letters from'a'
-'z'
. - The lengths of string
A
,B
andS
are between1
and1000
. - String
A
andB
are of the same length.
题解:
A and B are equal, for each index, the corresponding character in A and B should be in the same union.
When do the union, union by rank. a<c, a is c's parent.
Later, for each character of S, find its ancestor and append it to result.
Time Complexity: O((m+n)logm). m = A.length(), n = S.length(). find takes O(logm).
With path compression and union by rank, amatorize O(1).
Space: O(m).
AC Java:
class Solution {
Map<Character, Character> parent = new HashMap<>(); public String smallestEquivalentString(String A, String B, String S) {
for(int i = 0; i<A.length(); i++){
char a = A.charAt(i);
char b = B.charAt(i); if(find(a) != find(b)){
union(a, b);
}
} StringBuilder sb = new StringBuilder();
for(int i = 0; i<S.length(); i++){
char anc = find(S.charAt(i));
sb.append(anc);
} return sb.toString();
} private char find(char c){
parent.putIfAbsent(c, c);
if(c != parent.get(c)){
char anc = find(parent.get(c));
parent.put(c, anc);
} return parent.get(c);
} private void union(char a, char b){
char c1 = find(a);
char c2 = find(b);
if(c1 < c2){
parent.put(c2, c1);
}else{
parent.put(c1, c2);
}
}
}
最新文章
- 浅析tomcat nio 配置
- linux原始套接字(1)-arp请求与接收
- Android 编译时注解解析框架
- 模拟器的tableView的分割线不显示
- 理解perl的编码转换——utf8以及乱码
- FindResource函数错误代码:1813-找不到映像文件中指定的资源类型 与LoadResource函数错误代码:1812-指定的映像文件不包含资源区域
- maven项目:Invalid bound statement
- poj 1062 昂贵的聘礼(最短路 dijk+枚举)
- CentOS6.x机器安装Azure CLI2.0【1】
- redis数据类型-集合类型
- TCP/IP读书笔记(4) IPv4和IPv6 路由选择
- Python之操作MySQL数据库
- ext.net gridlist选择内部元素时自动选择所在行
- mybatis初始化过程
- Codeforces Round #481 (Div. 3)题解
- Django---简单from表单提交
- iOS开发--UILabel根据内容自动调整高度
- EasyUI+bootsrtap混合前端框架
- Thinkphp中查询复杂sql查询表达式,如何表达MYSQL中的某字段不为空is not null?
- import 语句用于导入从外部模块,另一个脚本等导出的函数,对象或原语。