常用字符串算法

Dear 丶 2021-09-28 19:42 350阅读 0赞

**一、判断两个字符串是否包含相同的内容**

1.巧用数组下标实现，把用字符的ASCII码值当作下标，记录出现的字符，然后对两字符串进行遍历

/**
         * 判断s于s2是否相同
         * @param s
         * @param s2
         * @return boolean
         */
        static boolean equals(String s,String s2) {
            if(s.length() != s2.length())return  false;
            int[] arr = new int[128];
            for(int i=0;i<s.length();i++) {
                arr[s.charAt(i)]++;
                arr[s2.charAt(i)]--;
            }
            for (int i : arr) {
                if(i != 0)return false;
            }
            return true;
        }

2.使用键值对TreeMap、HashMap或HashTable进行登记式记录，这个适用于文字等复杂的字符串

/**
         * TreeMap实现比较两个字符串包含的内容是否相同
         * @param s1
         * @param s2
         * @return
         */
        static boolean TreeMapEquals(String  s1,String s2) {
            if(s1.length()!= s2.length())return  false;
            TreeMap<Character,Integer> map = new  TreeMap<>();
            for(int i=0;i<s1.length();i++) {
                if(map.get(s1.charAt(i))== null) {
                    map.put(s1.charAt(i), 1);
                }
            }
            for(char c:s2.toCharArray()) {
                if(map.get(c) == null)return false;
            }
            return true;
        }

**二、判断一个字符串是否为另个一字符串的子集**

1.数组下标记录实现

/**
         * 检查两个字符串的子集是否具有相同的子集
         * @param sub 子集串
         * @param sup 匹配串
         * @return boolean
         */
        static boolean check(String sub,String sup)  {
            int[] asc = new int[128];
            for(int i=0;i<sup.length();i++) {
                if(asc[sup.charAt(i)]==0) {
                    asc[sup.charAt(i)] = 1;
                }
            }
            
            for(int i=0;i<sub.length();i++) {
                if(asc[sub.charAt(i)] != 1)
                    return false;
            }
            return true;
        }

2.键值对记录实现

/**
         * 使用HashMap实现
         * @param sub 子集串
         * @param sup 匹配串
         * @return
         */
        static boolean check_hash(String sub,String  sup) {
            Map<Character,Integer> map = new  HashMap<Character,Integer>();
            
            for(int i=0;i<sup.length();i++) {
                char ch = sup.charAt(i);
                if(map.get(ch)==null) {
                    map.put(ch, 1);
                }
            }
            for(int i=0;i<sub.length();i++) {
                if(map.get(sub.charAt(i)) != 1){
                    return false;
                }
            }
            return true;
        }

**三、去除字符串种出现k次的字符**

1.普通实现

/**
         * 在原串种删去指定个字符
         * @param s 原串
         * @param tar 目标字符
         * @param k 删除数量
         * @return
         */
        static String remove(String s,char tar,int  k) {
            char[] chars = s.toCharArray();
            int count = 0;
            StringBuilder sb = new  StringBuilder(chars.length);
            for(int i=0;i<chars.length;i++) {
                char c = chars[i];
                if(c == tar) {
                    count++;
                }else {
                    for(int j=0;j<count%k;j++) {
                        sb.append(tar);
                    }
                    sb.append(c);//把不等于tar的加入可变长字符串
                    count = 0;
                }
            }
            //循环结束后可能未遇见不等于tar的字符,所以肯还存在大于或小于k数量的tar字符
            for(int j=0;j<count%k;j++) {
                sb.append(tar);
            }
            return sb.toString();
        }

2.正则表达式替换实现

/**
         * 在原串种删去指定个字符
         * @param s 原串
         * @param tar 目标字符
         * @param k 删除数量
         * @return
         */
        static String remove2(String s,char tar,int  k) {
            return s.replaceAll(tar+"{"+k+"}", "");
        }

**四、字符串压缩统计**

形如aaaabbbbbccccc的可以写出a4b5c5，这就实现了对字符串的简单压缩，而有一些abc，写出a1b1c1明显比原串长因此不适用于这种算法，所以原串输出最合适。下面是这个算法的实现。

static String yasuo(String s) {
            char[] arr = s.toCharArray();
            int count = 0;
            int last = 0;
            StringBuilder sb = new  StringBuilder(arr.length);
            for(int i=0;i<arr.length;i++) {
                char ch= arr[i];
                if(sb.length()==0) {
                    sb.append(ch);
                    count++;
                }else {
                    if(last == ch) {
                        count++;
                    }else {
                        sb.append(count).append(ch);
                        count = 1;
                    }
                }
                last = ch;
            }
            //考虑最后一个字符
            if(count>1) {
                sb.append(count);
            }
            //StringBuilder的长度大于arr的长度时,返回短的原字符串s
            if(sb.length()>=arr.length) {
                return s;
            }
            return sb.toString();
        }