【Java -- 算法】字符串算法（一）

一、前言

本文介绍了有关字符串的算法第一部分的 Java 代码实现，算法实例：

• 替换字符串中的空格
• 输入一个字符串，打印出该字符串的所有排列
• 第一个只出现一次的字符
• 翻转句子
• 计算字符串之间的最短距离

所有代码均可通过 菜鸟工具在线编译器 直接运行，因此打算整理一下分享给大家。

二、代码 1. 替换字符串中的空格

问题描述

实现一个函数，将字符串p中的所有空格都替换成为指定的字符串r。

解决思路

• 遍历原始的字符串p，统计原先字符串中空格的个数spaceNum。
• 创建一个新的数组n，用于存放替换后的字符串。由于原先字符串中空格也占了一个位置，因此新数组n的长度为p.len + (r.len - 1) * spaceNum。
• 对于p 从后往前遍历，如果 遇到了空格，那么就将需要替换的字符串r中的字符 从后往前 填入n数组中；如果 遇到了非空格，那么就将p中的字符填入n数组中。

实现代码

class Untitled {
    static char[] replaceSpace(char p[], char r[], int pLen, int rLen){
        int spaceNum = 0;
        int i;
        for(i = 0; i = 0 && j >= 0){
            if (p[j] == ' ') {
                for (int k = rLen-1; k >= 0; k--)
                    n[i--] = r[k];
            } else {
                n[i--] = p[j];
            }
            j--;
        }
        n[nLen] = 0;
        return n;
    } 
    public static void main(String[] args) {
        char[] source = "I am sentence with space".toCharArray();
        char[] replace = "%20".toCharArray();
        char[] result = replaceSpace(source, replace, source.length, replace.length);
        System.out.println(result);
    }
}

运行结果

I%20am%20sentence%20with%20space

2. 输入一个字符串，打印出该字符串的所有排列

问题描述

输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

解决思路

这是一个 递归问题，求一个长度为n的字符串的全排列的方法为：

• n[0…n.len-1]全排列的计算方法为：将n[0]位置的字符分别和n[1…n.len-1]的每一个字符串交换，n[0]和交换后的n[1…n.len - 1]的全排列进行组合。我们将字符串{s}的全排列表示为{s}，那么对于abc来说，其全排列{abc}，就等于是a + {bc}、b + {ac}，c + {ba}。
• 以此类推，n[1…n.len - 1]的全排列，则是将n[1]分别和n[2…n.len - 1]的每一个字符串交换，再求出交换后的n[2…len - 1]的全排列，递归结束的条件为n[i…n.len - 1]只有一个字符，例如，bc的全排列为b + {c}、c + {b}，而{c}和{b}的全排列只有一种，因此递归结束，这时候就可以打印出结果。

实现代码

class Untitled {
    static void permutationStr(char p[], int depth, int length){
        if (depth == length) {
            System.out.println(p);
            return;
        }
        char c;
        for (int i = depth; i