确定两个字符串通过重新排序是否可以相同的算法

短命女 2022-07-25 23:29 166阅读 0赞

首先要确定字母是否区分大小写，是否要考虑空白字符？

**算法一：**  
此算法主要使用了JDK已有排序功能来实现的，考虑了空白字符，也区分了大小写。

/** * 判断两个字符串是否可以通过重新排序相等 * @author Administrator */
    public class CheckStringIsEquals { 
        public static void main(String[] args) {
            String s = "asdasdasdjjhhjkwerFF ";
            String t = "asdasdasdjjhhjkwerfF ";
            System.out.println(permutation(s,t));
        }
    
        public static String sort(String s){
            char[] content = s.toCharArray();
            java.util.Arrays.sort(content);
            return new String(content);
        }
    
        public static boolean permutation(String s,String t){
            if(s.length() != t.length()){
                return false;
            }
            return sort(s).equals(sort(t));
        }
    }

**算法二：**  
利用散列表的思想，使用字符的编码值当做下标来寻数组，将每个字符出现的次数记录下来，两个串进行比对。

/** * 判断两个字符串是否可以通过重新排序相等 * @author Administrator */
    public class CheckStringIsEquals { 
        public static void main(String[] args) {
            String s = "aa";
            String t = "a";
            System.out.println(permutation2(s,t));
        }
    
        public static boolean permutation2(String s,String t){
            //首先判断是否长度相等
            if(s.length() != t.length()){
                return false;
            }
    
            //假设只有256种字符
            int[] letters = new int[256];
    
            char[] s_array = s.toCharArray();
            //计算字符串s中每个字符出现的次数
            for(char c : s_array){
                letters[c]++;
            }
    
            for(int i = 0;i<t.length();i++){
                int c = (int)t.charAt(i);
                if(--letters[c]<0){
                    return false;
                }
            }
    
            return true;
        }
    }