常见字符串算法.md

###常见字符串算法 ####字符串字符判重算法

    package string;

	/**
	 * Created by zk on 2015/4/12.
	 * 判断字符串中是否包含重复字符，假设全为ASCII字符
	 */
	public class UniqueCharacter {
	    public static void main(String[] args) {
	        System.out.println(isUniqueCharacter("apple".toCharArray()));
	        System.out.println(isUniqueCharacter("abc%^".toCharArray()));
	        System.out.println(isUniqueSmallAlphabetChars("defghjkl".toCharArray()));
	        System.out.println(isUniqueSmallAlphabetChars("#$killer".toCharArray()));
	    }

    public static boolean isUniqueCharacter(char[] str) {
        if (str.length > 256)
            return false;

        //为每次字符，保留一个标记
        boolean[] charSet = new boolean[256];

        for (int i = 0; i < str.length; i++) {
            byte index = (byte) str[i];

            if (charSet[index]) {
                return false;
            }

            charSet[index] = true;
        }

        return true;
    }

    public static boolean isUniqueSmallAlphabetChars(char[] str) {
        if (str.length > 26) {
            return false;
        }

        // 使用位操作以改进空间占用
        int checker = 0;
        for (int i = 0; i < str.length; i++) {
            int index = str[i] - 'a';
            if (index < 0 || index > 26 || (checker & (1 << index)) > 0) {
                return false;
            }
            checker |= (1 << index);
        }

        return true;
    }
}

####字符串反转算法

package string;

/**
 * Created by zk on 2015/4/12.
 * 反转字符串
 */
public class ReverseString {
    public static void main(String[] args) {
        String text1 = "ABC1DEF";
        String text2 = "ABC1DEFG";
        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();

        reversePartOfString(t1, 1, t1.length - 2);
        reversePartOfString(t2, 1, t2.length - 2);

        String s1 = new String(t1);
        String s2 = new String(t2);

        System.out.println(s1);
        System.out.println(s2);

        String text3 = "ABC1DEF";
        String text4 = "ABC1DEFG";

        char[] t3 = text3.toCharArray();
        char[] t4 = text4.toCharArray();

        reverseArrayByXor(t3);
        reverseArrayByXor(t4);

        String s3 = new String(t3);
        String s4 = new String(t4);

        System.out.println(s3);
        System.out.println(s4);
    }

    public static void reversePartOfString(char[] str, int begin, int length) {
        char temp;

        for (int i = begin, j = begin + length - 1; i < j; i++, j--) {
            temp = str[i];
            str[i] = str[j];
            str[j] = temp;
        }
    }

    public static void reversePartOfStringWithWhile(char[] str, int begin, int length) {
        char temp;
        int i = begin;
        int j = begin + length - 1;

        while (i < j) {
            temp = str[i];
            str[i] = str[j];
            str[j] = temp;
            i++;
            j--;
        }
    }

    public static void reverseArray(char[] str) {
        char temp;

        for (int i = 0, j = str.length - 1; i < j; i++, j--) {
            temp = str[i];
            str[i] = str[j];
            str[j] = temp;
        }
    }

    public static void reverseArrayByXor(char[] str) {
        for (int i = 0, j = str.length - 1; i < j; i++, j--) {
            str[i] ^= str[j];
            str[j] ^= str[i];
            str[i] ^= str[j];
        }
    }
}

####左旋字符串

package string;

/**
 * Created by zk on 2015/4/12.
 *
 * @author zk
 *         给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，
 *         如把字符串 "abcdef" 前面的 2 个字符 'a' 和 'b' 移动到字符串的尾部，
 *         使得原字符串变成字符串 "cdefab"。要求对长度为 n 的字符串操作的时间复杂度为 O(n)，
 *         空间复杂度为 O(1)。
 *         </p>
 */
public class LeftRotateString {
    public static void main(String[] args) {
        String s1 = "abcdefg";
        String s2 = "abcdefgh";

        char[] a1 = s1.toCharArray();
        char[] a2 = s2.toCharArray();

        leftRotateString(a1, 2);
        leftRotateStringByGcd(a2, 2);

        String str1 = new String(a1);
        String str2 = new String(a2);

        System.out.println(str1);
        System.out.println(str2);
    }

    public static void leftRotateString(char[] str, int m) {
        reverseString(str, 0, m - 1);
        reverseString(str, m, str.length - 1);
        reverseString(str, 0, str.length - 1);
    }

    private static void reverseString(char[] str, int begin, int end) {
        char temp;
        int i = begin;
        int j = end;

        while (i < j) {
            temp = str[i];
            str[i] = str[j];
            str[j] = temp;
            i++;
            j--;
        }
    }

    /**
     * 求最大公约数
     * <p>
     * 假如整数n除以m，结果是无余数的整数，那么我们称m就是n的<em>约数</em>。
     * 需要注意的是，唯有被除数，除数，商皆为整数，余数为零时，此关系才成立。
     * 反过来说，我们称n为m的倍数。
     * </p>
     * <p>
     * <a>http://zh.wikipedia.org/wiki/最大公因數</a>
     * </p>
     *
     * @param m first number
     * @param n second number
     * @return 两个数的最大公约数
     */
    private static int gcd(int m, int n) {
        int k = m % n;

        if (k == 0) {
            return n;
        } else {
            return gcd(n, k);
        }
    }

    public static void leftRotateStringByGcd(char[] str, int m) {
        int n = str.length;
        int g = gcd(n, m);
        int e = n / g;

        char temp;
        for (int i = 0; i < g; i++) {
            temp = str[i];

            int j = 0;
            for (; j < e - 1; j++) {
                str[(i + j * m) % n] = str[(i + (j + 1) * m) % n];
            }

            str[(i + j * m) % n] = temp;
        }
    }
}

####右旋字符串

package string;

/**
 * Created by zk on 2015/4/12.
 * 给定一个字符串，要求把字符串后面的若干个字符移动到字符串的头部，
 * 如把字符串 "abcdef" 后面的 2 个字符 'e' 和 'f' 移动到字符串的头部，
 * 使得原字符串变成字符串 "efabcd"。要求对长度为 n 的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。
 * </p>
 */
public class RightRotateString {
    public static void main(String[] args) {
        String s1 = "abcdefg";
        String s2 = "abcdefgh";

        char[] t1 = s1.toCharArray();
        char[] t2 = s2.toCharArray();

        rightRotateString(t1, 2);
        rightRotateString(t2, 2);

        String str1 = new String(t1);
        String str2 = new String(t2);

        System.out.println(str1);
        System.out.println(str2);
    }

    public static void rightRotateString(char[] str, int m) {
        reverseString(str, 0, str.length - m - 1);
        reverseString(str, str.length - m, str.length - 1);
        reverseString(str, 0, str.length - 1);
    }

    private static void reverseString(char[] str, int begin, int end) {
        char temp;
        int i = begin;
        int j = end;

        while (i < j) {
            temp = str[i];
            str[i] = str[j];
            str[j] = temp;
            i++;
            j--;
        }
    }
}

####字符串旋转匹配算法

package string;

/**
 * Created by zk on 2015/4/12.
 * <p>
 * 给定两个字符串 s1 和 s2，如何判断 s1 是 s2 的一个旋转版本？
 * </p>
 */
public class RotateMatch {
    public static void main(String[] args) {
        String s1 = "apple";
        String s2 = "elppa";
        String s3 = "elppp";

        System.out.println(checkRotate(s1, s2));
        System.out.println(checkRotate(s1, s3));
    }

    public static boolean checkRotate(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;

        for (int i = 0, j = s2.length() - 1; i < s2.length(); i++, j--) {
            if (s1.charAt(i) != s2.charAt(j)) {
                return false;
            }
        }

        return true;
    }
}

####字符串包含算法

package string;

/**
 * Created by zk on 2015/4/12.
 * <p>
 * 给定两个分别由字母组成的字符串 s1 和字符串 s2，如何最快地判断字符串 s2 中所有字母是否都在字符串 s1 里？
 * </p>
 */
public class ContainString {
    public static void main(String[] args) {
        String s1 = "abcdefg";
        String s2 = "adg";
        String s3 = "kgl";

        System.out.println(isContainsAllChars(s1.toCharArray(), s2.toCharArray()));
        System.out.println(isContainsAllChars(s1.toCharArray(), s3.toCharArray()));
    }

    /**
     * 时间复杂度O(m + n)，空间复杂度O(1)
     *
     * @param s1
     * @param s2
     * @return
     */
    public static boolean isContainsAllChars(char[] s1, char[] s2) {
        int hash = 0;
        for (int i = 0; i < s1.length; i++) {
            hash |= (1 << (s1[i] - 'A'));
        }

        for (int i = 0; i < s2.length; i++) {
            if ((hash & (1 << (s2[i] - 'A'))) == 0) {
                return false;
            }
        }

        return true;
    }
}

####字符串原地替换算法

package string;

/**
 * Created by zk on 2015/4/12.
 * 将字符串 s1 中的某字符 p 全部替换成字符串 s2。假设 s1 字符数组尾部有足够的空间存放新增字符。
 */
public class ReplaceString {
    public static void main(String[] args) {
        char[] s1 = new char[100];
        for (int i = 0; i < 9; i += 3) {
            s1[i] = 'a';
            s1[i + 1] = 'b';
            s1[i + 2] = 'c';
        }

        System.out.println(new String(s1));
        replaceAllChars(s1, 9, 'b', "&^%".toCharArray());
        System.out.println(new String(s1));
    }

    public static void replaceAllChars(char[] s1, int s1Length, int p, char[] s2) {
        int count = 0;

        for (int i = 0; i < s1Length; i++) {
            if (s1[i] == p) {
                count++;
            }
        }

        int newLength = s1Length + s2.length * count;

        //从后向前进行替换，避免数据丢失
        for (int i = s1Length - 1; i >= 0; i--) {
            if (s1[i] == p) {
                for (int j = 0; j < s2.length; j++) {
                    s1[newLength - s2.length + j] = s2[j];
                }
                newLength = newLength - s2.length;
            } else {
                s1[newLength - 1] = s1[i];
                newLength = newLength - 1;
            }
        }
    }
}

####字符串压缩算法

package string;

	/**
 * Created by zk on 2015/4/12.
 * <p>
 * 给定字符串 s，要求将连续出现的字符压缩至字符和数量，并返回新的字符串。
 * <p/>
 * <p/>
 * 比如：s = "aabccccaaa"，则压缩后的字符串为 s2 = "a2b1c4a3"。
 * </p>
 */
public class CompressString {
    public static void main(String[] args) {
        String s1 = "aabccccaaa";
        System.out.println(s1);
        char[] s2 = compress(s1.toCharArray());
        System.out.println(new String(s2));

        String s3 = "aabccdeeaa";
        System.out.println(s3);
        char[] s4 = compress(s3.toCharArray());
        System.out.println(new String(s4));
    }

    public static char[] compress(char[] s) {
        //如果压缩后比原来还长，则不必压缩
        int size = countCompression(s);
        if (size > s.length) {
            return s;
        }

        //根据压缩后的长度创建数组
        char[] compressed = new char[size];

        int index = 0;
        char last = s[0];
        int count = 1;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == last) {
                count++;
            } else {
                index = appendChar(compressed, last, index, count);

                last = s[i];
                count = 1;
            }
        }

        index = appendChar(compressed, last, index, count);

        return compressed;
    }

    public static int appendChar(char[] array, char c, int index, int count) {
        //首先追加字符
        array[index] = c;
        index++;

        char[] countString = Integer.toString(count).toCharArray();

        //追加字符个数
        for (int i = 0; i < countString.length; i++) {
            array[index] = countString[i];
            index++;
        }

        return index;
    }

    /**
     * 计算压缩后字符串的长度
     *
     * @param str
     * @return
     */
    private static int countCompression(char[] str) {
        if (str == null || str.length == 0) {
            return 0;
        }

        int size = 0;
        int count = 1;
        int last = str[0];

        for (int i = 0; i < str.length; i++) {
            if (str[i] == last) {
                count++;
            } else {
                size += 1 + Integer.toString(count).length();

                last = str[i];
                count = 1;
            }
        }

        size += 1 + Integer.toString(count).length();

        return size;
    }
}

####变位词检测算法

package string;

/**
 * Created by zk on 2015/4/12.
 * 给定字符串 s1 和 s2，判断是否能够将 s1 中的字符重新排列后变成 s2。假设字符全部为小写 a-z 字符，
 * 字符串中没有空格。
 * <p/>
 * 变位词（anagram）：是由变换某个词或短语的字母顺序而构成的新的词或短语。
 * </p>
 */
public class Permutation {
    public static void main(String[] args) {
        System.out.println(isPermutation("hello".toCharArray(), "ehollu".toCharArray()));
        System.out.println(isPermutation("hello".toCharArray(), "eholu".toCharArray()));
        System.out.println(isPermutation("hello".toCharArray(), "eholl".toCharArray()));
    }

    public static boolean isPermutation(char[] s1, char[] s2) {
        if (s1.length != s2.length) {
            return false;
        }

        int[] letters = new int[256];
        for (int i = 0; i < s1.length; i++) {
            letters[s1[i]]++;
        }

        for (int i = 0; i < s1.length; i++) {
            letters[s2[i]]--;

            if (letters[s2[i]] < 0) {
                return false;
            }
        }

        return true;
    }
}

####字符串删除算法

package string;

/**
 * Created by zk on 2015/4/12.
 * <p>
 * 给定两个分别由字母组成的字符串 s1 和字符串 s2，将字符串 s2 中所有字符都在字符串 s1 中删除？
 * </p>
 */
public class DeleteString {
    public static void main(String[] args) {
        String s1 = "cdacbcdefabcdef";
        String s2 = "ab";

        String s3 = deleteString(s1, s2);

        System.out.println(s3);
    }

    public static String deleteString(String s1, String s2) {
        char[] a1 = s1.toCharArray();
        char[] a2 = s2.toCharArray();

        boolean[] table = new boolean[256];

        for (int i = 0; i < s2.length(); i++) {
            table[a2[i]] = true;
        }

        int faster = 0;
        int slower = 0;

        for (int i = 0; i < s1.length(); i++) {
            if (!table[a1[i]]) {
                a1[slower] = a1[faster];
                faster++;
                slower++;
            } else {
                faster++;
            }
        }

        return new String(a1, 0, slower);
    }
}

####字符串转整数算法

package string;

	/**
 * Created by zk on 2015/4/12.
 * <p>
 * 输入一个由数字组成的字符串，把它转换成整数并输出。例如：输入字符串 "123"，输出整数 123。
 * </p>
 */
public class StringToInteger {
    public static void main(String[] args) {
        System.out.println(StringToInt32("12345"));
        System.out.println(StringToInt32("-12345"));

        System.out.println(StringToInt32("2147483647"));
        System.out.println(StringToInt32("-2147483647"));

        System.out.println(StringToInt32("21474836470"));
        System.out.println(StringToInt32("-21474836470"));
    }

    public static int StringToInt32(String str) {
        if (str.length() > Integer.toString(Integer.MAX_VALUE).length()) {
            throw new IllegalArgumentException("字符串长度超出了整数的存储范围");
        }

        for (int i = 0; i < str.length(); i++) {
            if (!Character.isDigit(str.charAt(i)) && str.charAt(i) != '-') {
                throw new IllegalArgumentException("字符串包含非数字字符，无法转换成整数");
            }
        }

        if (str.length() == 0) {
            return 0;
        }

        char[] s = str.toCharArray();
        int value = 0;
        int i = 0;

        //检查是整数还是负数
        int sign = 1;
        if (s[0] == '+' || s[0] == '-') {
            if (s[0] == '-')
                sign = -1;
            i++;
        }

        while (i < s.length) {
            int c = s[i] - '0';

            if (sign > 0 && (value > Integer.MAX_VALUE / 10 ||
                    (value == Integer.MAX_VALUE / 10 && c >= Integer.MAX_VALUE % 10))) {
                value = Integer.MAX_VALUE;
                break;
            } else if (sign < 0 && (value > -(Integer.MIN_VALUE / 10) ||
                    (value == -(Integer.MIN_VALUE / 10) && c >= -(Integer.MIN_VALUE % 10)))) {
                value = Integer.MIN_VALUE;
                break;
            }

            value = value * 10 + c;

            i++;
        }

        return sign > 0 ? value : value == Integer.MIN_VALUE ? value : -value;
    }
}

####字符串全排列算法

package string;

	/**
 * Created by zk on 2015/4/12.
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * <p/>
 * 例如：输入字符串 "abc"，则输出由字符 'a', 'b', 'c'
 * 所能排列出来的所有字符串：abc, acb, bac, bca, cab, cba。
 */
public class AllPermutation {
    public static void main(String[] args) {
        //要求首次输入有序，否则需要排序
        calculateAllPermutations("abc".toCharArray());
    }

    public static void calculateAllPermutations(char[] s) {
        System.out.println(new String(s));

        int i, j;

        // 找到排列中最右一个升序的首位位置 i
        for (i = s.length - 2; (i >= 0) && (s[i] >= s[i + 1]); --i) ;

        //已经找到所有的排列
        if (i < 0)
            return;

        // 找到排列中第 i 位右边最后一个比 s[i] 大的位置 j
        for (j = s.length - 1; (j > i) && (s[j] <= s[i]); --j) ;

        //交换s[i],s[j]
        swap(s, i, j);

        // 将第 i + 1 位到最后的部分反转
        reverse(s, i + 1, s.length - 1);

        calculateAllPermutations(s);
    }

    //交换数组中两个位置的元素
    private static void swap(char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    //反转数组
    private static void reverse(char[] s, int start, int end) {
        char temp;
        int i = start;
        int j = end;

        while (i < j) {
            temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            j--;
        }
    }
}

####字符串字典序组合算法

package string;

	/**
 * Created by zk on 2015/4/13.
 * 输入一个字符串，字符串里的字符是互不相同的，打印出该字符串中字符按照字典序输出所有的组合。
 * <p/>
 * 例如：输入字符串 "ab"，则输出由字符 'a', 'b' 所能排列出来的所有字符串：aa, ab, ba, bb。
 */
public class DictionaryString {
    public static void main(String[] args) {
        //要求字符是不同的，否则需要去重
        //要求输入是有序的，否则需要排序
        calculateRepeatablePermutations("abc".toCharArray(), new char[3], 0);
    }

    public static void calculateRepeatablePermutations(char[] s, char[] permutation, int p) {
        //如果只剩下一个字符
        if (p == s.length) {
            System.out.println(new String(permutation));
        } else {
            for (int i = 0; i < s.length; i++) {
                permutation[p] = s[i];
                calculateRepeatablePermutations(s, permutation, p + 1);
            }
        }
    }
}

####字符串的（括号）生成算法

package string;


import java.util.ArrayList;
import java.util.List;

/**
 * Created by zk on 2015/4/13.
 * 输出n对括号的有效组合
 */
public class ParenString {
    public static void main(String[] args) {
        List<String> parenList = generateParens(3);

        for (String s : parenList) {
            System.out.println(s);
        }
    }

    public static List<String> generateParens(int count) {
        char[] str = new char[count * 2];
        List<String> list = new ArrayList<>();
        addParen(list, count, count, str, 0);
        return list;
    }

    public static void addParen(List<String> list,
                                int leftRem,
                                int rightRem,
                                char[] str,
                                int count) {
        //无效状态
        if (leftRem < 0 || rightRem < leftRem) {
            return;
        }

        if (leftRem == 0 && rightRem == 0) {
            String s = new String(str);
            list.add(s);
        } else {
            //还有左括号可用
            if (leftRem > 0) {
                str[count] = '(';
                addParen(list, leftRem - 1, rightRem, str, count + 1);
            }
            //还有右括号可用
            if (rightRem > leftRem) {
                str[count] = ')';
                addParen(list, leftRem, rightRem - 1, str, count + 1);
            }
        }
    }
}