字符串相关算法

1.字符串翻转

//实现字符串的反转 ，例如how are you 变 you are how
// 以及单词的反转，单词的反转即是先全部反转，然后在把每个单词反转

public class StringReverse {
    public static void main(String[] args){
        String str = "how are you";
//        StringBuffer sb =new StringBuffer();
//        sb.append(str);
//        String str2 = sb.reverse().toString();
//        System.out.println(str2);
        System.out.println(swapWords(str));
    }
    public static void swap(char[] cArr,int front,int end){
        while(front < end){
            char tmp = cArr[end];
            cArr[end] = cArr[front];
            cArr[front] = tmp;
            front++;
            end--;
        }
    }

    public static String swapWords(String s) {
        char[] cArr = s.toCharArray();
        //对整个字符串进行字符翻转
        swap(cArr, 0, cArr.length - 1);

        int begin = 0;
        //对每个单词进行字符串翻转操作
        for (int i = 1; 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);
    }
}

2.统计字符串中单词个数

/
统计一个字符串中出现单词的个数
单词的前一个字符为空才代表出现的是单词。只需要用一个标志位记录前一个是否是空格即可 /

public class StringWordCount {
    public static void main(String[] args){
        String s = "  hello    wolrd";
        System.out.println(wordCount(s));
    }

    public static int wordCount(String s){
        int count = 0;
        int word=0;//word为0表示前一个字符是空格，1表示非空格
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)==' '){
                word = 0;
            }else if (word==0){
                //只有前一位是空格意味着是一个单词，如果去掉word==0条件就变成统计字符了
                word = 1;
                count++;
            }
        }
        return count;
    }
}

3.字符串去重

/
删除字符串中重复的字符如good应该变成god
此问题也有两种办法第一蛮力遍历把重复的先变为’\0’，再去掉
方法二空间换时间因为字符个数也是256，也可以根据记录个数去重(另提供更节省空间的法三) /

public class StringRemoveDuplicate {
    public static void main(String[] args){
        String s = "ggooddgg";
        System.out.println(removeDuplicate1(s));
        System.out.println(removeDuplicate2(s));
    }

    //方法三在方法二的基础上知道我们需要256大小的空间，每1bit记录一个字符是否存在，
    //更好的方案是我们申请一个大小为8的int型数组，每个int 32位，32x8=256
    public static String removeDuplicate3(String s){
        char[] c = s.toCharArray();
        int len = c.length;
        int []flags = new int[8];

        for (int i = 0; i < 8; i++) {
            flags[i] = 0;
        }
        for (int i = 0; i < len; i++) {
            int index = (int)c[i]/32;
            int shift = (int)c[i]%32;
            if((flags[index]&(1<<shift))!=0){
                c[i] = '\0';
            }
            flags[index] |= (1<<shift);
        }
        int l=0;
        for (int i = 0; i < len; i++) {
            if(c[i]!=0){
                c[l++] = c[i];
            }
        }
        return new String(c,0,1);

    }
    //方法二空间换时间
    public static String removeDuplicate2(String s1){
        char[] c = s1.toCharArray();
        StringBuffer sb = new StringBuffer();
        int[] cCout = new int[256];
        //初始化都为0，如果后面的遇到为1那么说明前面已经存在
        for (int i = 0; i < 256; i++) {
            cCout[i] = 0;
        }
        for (int i = 0; i < c.length; i++) {
            if (cCout[c[i]] == 1){
                continue;
            }
            sb.append(c[i]);
            cCout[c[i]] = 1;
        }
        return sb.toString();
    }

    //方法一蛮力法
    public static String removeDuplicate1(String s1){
        char[] c = s1.toCharArray();

        //重复的数字置换为'\0'
        for (int i = 0; i < c.length; i++) {
            for (int j = i+1; j < c.length; j++) {
                if (c[i]==c[j]){
                    c[j]= '\0';
                }
            }
        }

        //去掉‘\0’
        int k=0;
        for (int i = 0; i < c.length; i++) {
            if (c[i]!='\0'){
                c[k++] = c[i];
            }
        }
        return new String(c,0,k);
    }

}

4.字符的组合

/
求例如输入字符串abc，那么a、b、c三个字符共有多少种组合（假设字符串中所有字符都不重复）
a、b、c、ab、ac、bc、abc
此题我们就不考虑暴力的解法了
//方法一：递归
//方法二：用二进制数来表示字符的出现与不出现如011代表bc,111代表abc,100代表a /

public class StringCombine {
    public static void main(String[] args){
        String s = "abc";
        char[] c = s.toCharArray();
        StringBuffer sb = new StringBuffer("");
        int len = c.length;
        for (int i = 1; i <= len; i++) {
            combineRecursiveImpl(c,0,i,sb);
        }
        System.out.println("-------------------------------");
        combine(c);
    }

    private static void combine(char[] c) {
        if (c==null)
            return;
        int len = c.length;
        boolean used[] = new boolean[len];
        char cache[] = new char[len];
        int result = len;
        while (true){
            int index = 0;
            while(used[index]){
                used[index] = false;
                ++result;
                if(++index==len)
                    return;
            }
            used[index] = true;
            cache[--result] = c[index];
            System.out.print(new String(cache).substring(result) + " " );
        }
    }

    private static void combineRecursiveImpl(char[] c, int begin, int len, StringBuffer sb) {
        if(len==0){
            System.out.println(sb+" ");
            return;
        }
        if (begin==c.length){
            return;
        }
        sb.append(c[begin]);
        combineRecursiveImpl(c,begin+1,len-1,sb);//取该字符的情况
        sb.deleteCharAt(sb.length()-1);
        combineRecursiveImpl(c,begin+1,len,sb);//不取该字符的情况
    }
}

5.字符串大小比较

/
判断两个字符串是否有相同的字符组成 如aaaabbc与abcbaaa就是。组成字符及个数都相同
解决此问题有两种方法法一就是将他们排序，然后比较两个字符串是否相等
方法二：时间换空间也就是桶记录他们每个字符的个数以及是否存在来确定 /

public class StringCompare {
    public static void main(String[] args){
        String s1 = "aaaabc";
        String s2 = "abcaaa";

        compareMethod1(s1,s2);
        compareMethod2(s1,s2);
    }

    public static void compareMethod2(String s1, String s2){
        byte[] b1 = s1.getBytes();
        byte[] b2 = s2.getBytes();
        int cCout[] = new int[256];//因为字符数一共256个，所以足够了

        for (int i = 0; i < 256; i++) {
            cCout[i] = 0;
        }

        for (int i = 0; i < b1.length; i++) {
            cCout[b1[i] - '0']++;
        }
        for (int i = 0; i < b2.length; i++) {
            cCout[b1[i] - '0']--;
        }
        for (int i = 0; i < 256; i++) {
            if (cCout[i]!=0){
                System.out.println("not euqal 2");
                return;
            }
        }
        System.out.println("euqal 2");

    }

    public static void compareMethod1(String a,String b){
        byte[] b1 = a.getBytes();
        byte[] b2 = a.getBytes();
        Arrays.sort(b1);
        Arrays.sort(b2);
        a = new String(b1);
        b = new String(b2);

        if(a.equals(b)){
            System.out.println("equal!");
        }else {
            System.out.println("not equal!");
        }

    }
}

6.字符的全排列

针对1,2,2,3,4,5这六个数字，写成一个函数，打印出所有不同的排列，例如512234,215432,
要求“4”不能在第三位，“3”与“5”不能相连。

另给出 1,2，3组成全排列无限制方法

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * Created by FangHeart on 2017/3/1.
 */
/*
    针对1,2,2,3,4,5这六个数字，写成一个函数，打印出所有不同的排列，例如512234,215432,
    要求“4”不能在第三位，“3”与“5”不能相连。
 */
/*
*   另给出 1,2，3组成全排列无限制方法
* */
public class StringCobinations {
    private int[] numbers = new int[]{1,2,2,3,4,5};
    private int n = numbers.length;

    //用来标记图中的节点是否被便利过
    private boolean[] visted = new boolean[n];

    //图中的二维数组表示
    private int [][]graph = new int[n][n];
    //数字的组合
    private String combination = "";
    public Set <String> getAllCombinations(){
        //构造图
        buildGraph();
        //用来存放所有组合
        Set<String> set = new HashSet<String>();
        //分别从不同的节点出发深度遍历图
        for (int i = 0; i < n; i++) {
            this.depthFirstSearch(i,set);
        }
        return set;
    }
    private void buildGraph(){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i==j){
                    graph[i][i] = 0;
                }else {
                    graph[i][j] = 1;
                }
            }
        }

        //确保在遍历时3与5是不可达的
        graph[3][5]=0;
        graph[5][3]=0;
    }

    //对树从节点start位置开始进行深度遍历
    private void depthFirstSearch(int start,Set<String> set){
        visted[start] = true;
        combination = combination + numbers[start];
        if (combination.length()==n){
            //4不能出现在第三个位置
            if (combination.indexOf("4")!=2)
                set.add(combination);
        }
        for (int i = 0; i < n; i++) {
            if (graph[start][i]==1 && visted[i]==false)
                depthFirstSearch(i,set);
        }
        combination = combination.substring(0,combination.length()-1);
        visted[start]=false;
    }


    public static void main(String[] args){

        StringCobinations stringCobinations = new StringCobinations();
        Set<String> set = stringCobinations.getAllCombinations();
        Iterator<String> it = set.iterator();
        while(it.hasNext()){
            String string = (String)it.next();
            System.out.println(string);
        }

        int a[] = new int[]{1,2,3};
        perm(a,0,a.length-1);

    }


    //算法思路n各元素全排列= （n-1个元素的全排列）+另一个元素为前缀
    //出口：如果只有一个元素全排列，说明已经完成
    public static void perm(int arr[], int begin,int end) {
        if(end==begin){         //一到递归的出口就输出数组，此数组为全排列
            for(int i=0;i<=end;i++){
                System.out.print(arr[i]+" ");
            }
            System.out.println();
            return;
        }
        else{
            for(int j=begin;j<=end;j++){
                swap(arr,begin,j);      //for循环将begin~end中的每个数放到begin位置中去
                perm(arr,begin+1,end);  //假设begin位置确定，那么对begin+1~end中的数继续递归
                swap(arr,begin,j);      //换过去后再还原
            }
        }
    }

    private static void swap(int[] a,int s,int i) {
        int t=a[s];
        a[s]=a[i];
        a[i]=t;

    }



}

7.字符串的全排列

/*

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。 /
*/

public ArrayList<String> Permutation(String str) {
    ArrayList<String> arrayList = new ArrayList<String>();
    HashSet<String> hashSet = new HashSet<String>();
    if (str!=null && str.toCharArray().length>0){
        PermutationHelper(str.toCharArray(),0,hashSet);
    }
    arrayList.addAll(hashSet);
    Collections.sort(arrayList);
    return arrayList;
}

public void PermutationHelper(char[] chars, int i, HashSet<String> hashSet) {
    if (i==chars.length-1){
        hashSet.add(new String(chars));
    }else {
        for (int j = i; j < chars.length; j++) {
            swap(chars,i,j);
            PermutationHelper(chars,i+1,hashSet);
            swap(chars,i,j);
        }
    }
}

public void swap(char[] chars, int i, int j) {
    if (i != j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}

8.字符串是否含有子字符串(KMP算法)

public static boolean KMP(String str,String subStr){
        String newStr = "x" + str;
        String newSubStr = "x" + subStr;

        int i = 1;
        int j = 1;

        int []K = calK(subStr);

        while (i<=str.length()&&j<=subStr.length()){
            if (j==0||newStr.charAt(i)==newSubStr.charAt(j)){
                i++;
                j++;
            }else {
                j = K[j];
            }
        }
        if (j>subStr.length())
            return true;
        else
            return false;
    }
    public static int[] calK(String subString){
        String newSubStr = "x" + subString;
        int K[] = new int[newSubStr.length()];

        int i = 1;
        K[1] = 0;
        int j = 0;
        while (i<subString.length()){
            if (j==0||newSubStr.charAt(i)==newSubStr.charAt(j)){
                i++;
                j++;
                K[i] = j;
            }else {
                j = K[j];
            }
        }
        return K;
    }

9.动态规划解决最大公共子串

/*
这是一道标准的动态规划问题，求两个字符串的最大公共子串
例如 String a = “abcde”
String b = “abc”
那么最长公共子串为abc

可以建立一个二维数组p[i][j]代表到达字符串1的位置，字符串j位置时候的最大公共字符串
可以得到如下公式
            | "" (String1char[i]!=String2char[j])
p[i][j]=    | String1char[i]或者String2char[j]  (i=0或者j=0)
            | p[i-1][j-1] + char (String1char[i]==String2char[j])

*/

public class MaxSubString {

    @Test
    public void test(){
        System.out.println(getSubString("abcdaasdjhjkasdaa","abcasfsadsdaa"));
    }
    public String getSubString(String str1,String str2){
        int len1 = str1.length();
        int len2 = str2.length();

        int maxLen = 0;
        String lcs = "";

        char char1,char2;
        String p[][] = new String[len1][len2];
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                char1 = str1.charAt(i);
                char2 = str2.charAt(j);

                if (char1!=char2)
                    p[i][j] = "";
                else {
                        if (i == 0)
                            p[i][j] = String.valueOf(char1);
                        else if (j == 0)
                            p[i][j] = String.valueOf(char2);
                        else
                            p[i][j] = p[i - 1][j - 1] + String.valueOf(char1);

                        if (p[i][j].length()>maxLen){
                            maxLen = p[i][j].length();
                            lcs = p[i][j];
                        }else if (p[i][j].length()==maxLen){
                            lcs = lcs +","+p[i][j];
                        }
                }
            }
        }
        return lcs;

    }
}

10.动态规划解决最长回文长度

/*
题目：所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，
比如：”aba”，”abba”.对于一个字符串，可以通过删除某些字符二编程回文字符串，
如：“cabebaf”,删除“c,e,f”后剩下子串“abba”就是回文字符串。
要求：给定任意一个字符串，字符串的最大长度1000，计算出最长的回文字符串长度。
输入：字符串
输出：最大的回文字符串的长度。

分析：回文即是从前到中和从后到中完全一致
那么如果第一个字符和最后一个字符相等，那么最长回文串长度就是中间的最长回文串+2
如果第一个字符和最后一个字符不相等，那么最长子串的长度就是去掉头字符的最长子字符串和去掉尾结点的最长子字符串长度
既有方程
|p[i+1][j-1] + 2;(char[i]==char[j] i<j)
p[i][j]= |p[i+1][j-1] + 1;(char[i]==char[j] i==j中间单个字符)
|max(p[i+1][j],p[i][j-1])

为了方便写循环
p[i][j]代表j-i之间最大回文的长度，
*/

public class MaxlengthHuiWen {

    @Test
    public void test(){
        getLen("cabebaf");
        getLen2("cabebaf");
    }
    public void getLen2(String s){

        char c[] = (" "+s + " ").toCharArray();
        int n = c.length;
        int p[][] = new int[n][n];
        int maxLen = 0;

        for (int i = n-2; i >= 1; i--) {
            for (int j = 1; j <= i; j++) {
                if (c[i]==c[j]&&i>j){
                    p[i][j]= p[i+1][j-1] + 2;
                }else if (c[i]==c[j]&&i==j){
                    p[i][j] = p[i+1][j-1] + 1;
                }else if(p[i+1][j]>=p[i][j-1]){
                    p[i][j] = p[i+1][j];
                }else
                    p[i][j] = p[i][j-1];
                if (p[i][j] > maxLen)
                    maxLen = p[i][j];
            }
        }
        System.out.println(maxLen);
    }
    public void getLen(String s){

        char c[] = (" "+s + " ").toCharArray();
        int n = c.length;
        int p[][] = new int[n][n];
        int maxLen = 0;

        for (int i = 1; i < n-1; i++) {
            for (int j = n-2; j >=i ; j--) {
                if (c[i]==c[j]&&i<j){
                    p[i][j]= p[i-1][j+1] + 2;
                }else if (c[i]==c[j]&&i==j){
                    p[i][j] = p[i-1][j+1] + 1;
                }else if(p[i-1][j]>=p[i][j+1]){
                    p[i][j] = p[i-1][j];
                }else
                    p[i][j] = p[i][j+1];
                if (p[i][j] > maxLen)
                    maxLen = p[i][j];
            }
        }
        System.out.println(maxLen);
    }
}