描述
对于两个字符串A和B,如果A和B中出现的字符种类相同且每种字符出现的次数相同,则A和B互为变形词,请设计一个高效算法,检查两给定串是否互为变形词。
给定两个字符串A和B及他们的长度,请返回一个bool值,代表他们是否互为变形词。
测试样例:
"abc",3,"bca",3
返回:true
解法
使用一个HashMap记录字符出现的次数
第一遍遍历A,将字符出现的次数记录到map中
第二次遍历B,将map中的次数减去,如果有map中不存在的字符,或者map中记录的次数小于B中的次数,返回false
public boolean chkTransform(String A, int lena, String B, int lenb) {
if (lena != lenb)
return false;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < A.length(); i++) {
if (map.containsKey(A.charAt(i))) {
map.put(A.charAt(i), map.get(A.charAt(i)) + 1);
} else {
map.put(A.charAt(i), 1);
}
}
for (int i = 0; i < B.length(); i++) {
if (!map.containsKey(B.charAt(i)) || map.get(B.charAt(i)) <= 0) {
return false;
} else {
map.put(B.charAt(i), map.get(B.charAt(i)) - 1);
}
}
return true;
}
网友评论