[java实现]常见算法之字符串操作

灰太狼 2021-12-20 16:15 248阅读 0赞

### 一、字符串反转 ###

把一个句子中的打次进行反转，比如“how are you” ,变为 “you are how”

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

// 字符串反转
    public class StringTest {
    
        // 字符反转的方法
        private void swap(char[] c, int front, int end) {
    
            if (front > end || end >= c.length) {
                return;
            }
    
            while (front < end) {
    
                char tmp = c[front];
                c[front] = c[end];
                c[end] = tmp;
    
                front++;
                end--;
            }
        }
    
        // O(n)
        public String swapStr(String str) {
    
            char[] cArr = str.toCharArray();
    
            // 整个字符串的字符反转
            swap(cArr, 0, cArr.length - 1); // 反转整个字符串中的所有字母，how are you -> uoy era woh
    
            int begin = 0;
    
            // 对字符串中的每个单词反转，除了最后一单词
            for (int i = 0; i < cArr.length; i++) {
    
                if (cArr[i] == ' ') {
                    swap(cArr, begin, i - 1);
                    begin = i + 1;
                }
            }
    
            // 最后一个单词的反转
            swap(cArr, begin, cArr.length - 1);
    
            return new String(cArr);
        }
    
        public static void main(String[] args) {
    
            String str = "how are you";
            System.out.println(new StringTest().swapStr(str));
        }
    
    }

### 二、判断字符串是否由相同的字符组成 ###

判断连个字符串的字母个字母的个数是否一样，顺序可以不同， 如“aaaabc” 和“cbaaaa”是相同的

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

// 判断字符串是否由相同的字符组成
    public class StringTest {
    
        // 方法一 可以死任意字符      O(nlogn)
        public boolean compareStr(String str1, String str2) {
    
            byte[] bs1 = str1.getBytes();
            byte[] bs2 = str2.getBytes();
    
            Arrays.sort(bs1);
            Arrays.sort(bs2);
    
            str1 = new String(bs1);
            str2 = new String(bs2);
    
            if (str1.equals(str2)) {
                return true;
            } else {
                return false;
            }
        }
    
        // 只能是ASCII码  方法二  O(n)
        public boolean compareStr2(String str1, String str2) {
    
            byte[] bs1 = str1.getBytes();
            byte[] bs2 = str2.getBytes();
    
            int bCount[] = new int[256];
    
            for (int i = 0; i < bs1.length; i++)
                bCount[bs1[i] ]++;
            for (int i = 0; i < bs2.length; i++)
                bCount[bs2[i] ]--;
            for (int i = 0; i < 256; i++) {
    
                if (bCount[i] != 0) {
                    return false;
                }
    
            }
            return true;
    
        }
    
        public static void main(String[] args) {
    
            String str1 = "aaaabbc";
            String str2 = "cbaaaab";
    
            System.out.println(new StringTest().compareStr2(str1, str2));
    
        }
    
    }

### 三、字符串中单词的统计 ###

给定一段空格分开的字符串，判断单词的个数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

// 字符串中单词的统计
    public class StringTest {
    
        // O(n)
        public int wordCount(String str) {
    
            int word = 0;
            int count = 0;
            for (int i = 0; i < str.length(); i++) {
    
                if (str.charAt(i) == ' ')
                    word = 0;
                else if (word == 0 ) {
                    word = 1;
                    count++;
                }
            }
    
            return count;
        }
    
        public static void main(String[] args) {
    
            String str = "i am a good boy";
    
            System.out.println(new StringTest().wordCount(str));
    
        }
    
    }

### 四、删除字符串中重复的字符 ###

删除字符串中国重复的字符。如good -> god

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

// 删除字符串中重复的字符
    public class StringTest {
    
        // O(n^2)
        public String removeDuplicate(String str) {
    
            char[] cs = str.toCharArray();
            int n = cs.length;
    
            for (int i = 0; i < n; i++) {
    
                if (cs[i] == '\0')
                    continue;
    
                for (int j = i + 1; j < n; j++) {
    
                    if (cs[j] == '\0')
                        continue;
                    if (cs[i] == cs[j])
                        cs[j] = '\0';
                }
            }
    
            int be = 0;
            for (int i = 0; i < n; i++) {
                if (cs[i] != '\0')
                    cs[be++] =cs[i];
            }
            
            return new String(cs, 0, be);
        }
    
        // 方法二： O(n)
        public String removeDuplicate2(String str) {
    
            char[] cs = str.toCharArray();
            int n = cs.length;
            
            int count[] = new int[256];
            for (int i = 0; i < cs.length; i++) {
                if (count[cs[i]] != 0)
                    cs[i] = '\0';
                count[cs[i]]++;
            }
    
            int be = 0;
            for (int i = 0; i < n; i++) {
                if (cs[i] != '\0')
                    cs[be++] = cs[i];
            }
    
            return new String(cs, 0, be);
        }
    
        public static void main(String[] args) {
    
            String str = "aaaabbc";
    
            System.out.println(new StringTest().removeDuplicate(str));
    
        }
    
    }

### 五、按要求打印给定数组的排列情况 ###

如1，2,2,3,4,5，要求第四位不为4,3和5不能相连

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

// 按要求打印数组的排列情况
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.Set;
    
    public class StringTest {
    
        boolean visited[];
        String combination = "";
        int graph[][] = null;
    
        public void getAllCombination(int arr[]) {
    
            int n = arr.length;
            graph = new int[n][n];
            visited = new boolean[n];
    
            buildGraph(arr, graph);
    
            Set<String> set = new HashSet<>();
    
            for (int i = 0; i < n; i++) {
                depthFirstSearch(i, set, arr);
            }
    
            Iterator<String> iterator = set.iterator();
    
            while (iterator.hasNext()) {
                String string = (String) iterator.next();
                System.out.println(string);
            }
        }
    
        /**
         * 按照深度优先遍历 图，将符合要求的组合加入到set中，自动去重
         * 
         * @param start
         * @param set
         * @param arr
         */
        private void depthFirstSearch(int start, Set<String> set, int arr[]) {
            visited[start] = true;
            combination += arr[start];
    
            if (combination.length() == arr.length) {
                if (combination.indexOf("4") != 2) {
                    set.add(combination);
                }
            }
    
            for (int j = 0; j < arr.length; j++) {
                if (graph[start][j] == 1 && visited[j] == false)
                    depthFirstSearch(j, set, arr);
            }
    
            // 什么意思?
            combination = combination.substring(0, combination.length() - 1);
            visited[start] = false;
        }
    
        /**
         * 根据传入的数构建一个图，图中的 3,5 不能相连
         * 
         * @param arr
         * @param graph
         * @return
         */
        private int[][] buildGraph(int arr[], int[][] graph) {
    
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr.length; j++) {
                    if (arr[i] == arr[j])
                        graph[i][j] = 0;
                    else
                        graph[i][j] = 1;
                }
            }
    
            graph[3][5] = 0;
            graph[5][3] = 0;
    
            return graph;
        }
    
        public static void main(String[] args) {
    
            int arr[] = { 1, 2, 2, 3, 4, 5 };
            new StringTest().getAllCombination(arr);
    
        }
    
    }

### 六、输出字符串的所有组合 ###

给定一个字符串，输出该字符串中字符的所有组合

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

// 输出字符串的所有组合
    
    public class StringTest {
    
        public void combineRecursive(char[] c, int begin, int len, StringBuffer sb) {
    
            if (len == 0) {
                System.out.print(sb + " ");
                return;
            }
    
            if (begin == c.length)
                return;
            sb.append(c[begin]);
            combineRecursive(c, begin + 1, len - 1, sb);
            sb.deleteCharAt(sb.length() - 1);
            combineRecursive(c, begin + 1, len, sb);
    
        }
    
        public static void main(String[] args) {
    
            String s = "abc";
            char[] cs = s.toCharArray();
            StringBuffer sb = new StringBuffer();
    
            for (int j = 1; j < cs.length; j++) {
                new StringTest().combineRecursive(cs, 0, j, sb);
            }
        }
    
    }

转载于:https://www.cnblogs.com/ytuan996/p/10679288.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/e400fe22d0924632a4ccbb37ea452b3d.png