Leetcode刷题之旅--面试题 01.02. 判定是否互为字符重排
程序员文章站
2024-03-04 09:15:29
...
题目描述:
最简单的想法就是用hashmap来记录各个字符出现次数。
import java.util.HashMap;
public class Solution {
public static void main(String[] args) {
String s1="abc";
String s2="bab";
System.out.println(new Solution().CheckPermutation(s1,s2));
}
public boolean CheckPermutation(String s1, String s2) {
boolean flag=true;
HashMap<Character,Integer> hashMap=new HashMap<>();
for (int i=0;i<s1.length();i++){
if (hashMap.containsKey(s1.charAt(i))) hashMap.put(s1.charAt(i),hashMap.get(s1.charAt(i))+1);
else hashMap.put(s1.charAt(i),1);
}
for (int i=0;i<s2.length();i++){
if (hashMap.containsKey(s2.charAt(i))) hashMap.put(s2.charAt(i),hashMap.get(s2.charAt(i))-1);
else return false;
}
for (int i=0;i<s1.length();i++){
if (hashMap.get(s1.charAt(i))!=0){
flag=false;
break;
}
}
return flag;
}
}
这种方法由于遍历的三次所以时间复杂度会较高
看了下题解区,比较好的解法(不算python),用两个数组来表示各个字符(比如说每个位置按ascii码来分给各个字符),最后看数组各个元素是否等于0。这样可以两个字符串遍历一起进行,时间复杂度会降低很多。