字符串相关操作 使用KMP算法对字符串进行匹配 【字符串】【Java】【leetcode】【KMP】

字符串简介

字符串实际上是一个unicode 字符数组。你可以执行几乎所有我们在数组中使用的操作。
然而，二者之间还是存在一些区别。在这篇文章中，我们将介绍一些在处理字符串时应该注意的问题。这些特性在不同的语言之间可能有很大不同。

字符串的三个练习

1、实现strStr() （ Implement strStr()）

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
	当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
	对于本题而言，当 needle 是空字符串时我们应当返回 0 。
	这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

使用KMP算法构造next数组帮助比对

class Solution {
    public int strStr(String haystack, String needle) {
        char[] res = haystack.toCharArray();
        char[] wait = needle.toCharArray();
        if (needle.length() == 0) {
            return 0;
        }
        int resL = res.length;
        int waitL = wait.length;
        if (resL < waitL) {
            return -1;
        }
        int i = 0;
        int j = 0;

        int[] next = getNext(needle);

        while (i < resL && j < waitL) {
            if (res[i] == wait[j]) {
                i++;
                j++;
            } else {
                if (j > 0) {
                    j = next[j - 1];
                } else {
                    j = 0;
                    i++;
                }
            }
        }
        if (j == waitL) {
            return i - j;
        } else {
            return -1;
        }
    }
    public int[] getNext(String pattern) {
        if (pattern.length() == 1) {
            return new int[]{1};
        }
        char[] ele = pattern.toCharArray();
        int length = ele.length;
        int[] next = new int[length];
        next[0] = 0;

        int i = 1;
        int j = 0;
        while (i < length) {
            if (ele[i] == ele[j]) {
                j++;
                next[i] = j;
                i++;
            } else {
                while (j != 0 && ele[i] != ele[next[j - 1]]) {
                    j = next[j - 1];
                }
                next[i] = j;
                i++;
            }
        }
        return next;
    }
}

2、二进制求和（Add Binary）

给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。

示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"

class Solution {
    public String addBinary(String a, String b) {
        char[] start = a.toCharArray();
        char[] end = b.toCharArray();
        List<Character> st = new ArrayList<>();
        int stL = start.length;
        List<Character> ed = new ArrayList<>();
        int edL = end.length;
        LinkedList<Character> res = new LinkedList<>();
        for (char ch : start) {
            st.add(ch);
        }
        for (char ch : end) {
            ed.add(ch);
        }
//        定义一个int，大小为start和end中短的那个
        int min = stL > edL ? edL : stL;

        //定义一个状态
        int status = 0;

        for (int i = 0; i < min; i++) {
            if (st.get(stL - i-1).equals(ed.get(edL - i-1))) {
                if (st.get(stL - i-1).equals('0')) {
                    if (status == 0) {
                        res.addFirst('0');
                        status = 0;
                    } else {
                        res.addFirst('1');
                        status = 0;
                    }

                } else {
                    if (status == 0) {
                        res.addFirst('0');
                        status = 1;
                    } else {
                        res.addFirst('1');
                        status = 1;
                    }

                }
            } else {
                if (status == 0) {
                    res.addFirst('1');
                    status = 0;
                } else {
                    res.addFirst('0');
                    status = 1;
                }
            }
        }
        if (edL == stL) {
            if (status == 1) {
                res.addFirst('1');
                String out = "";
                for (char ch : res) {
                    out = out + ch;
                }
                return out;
            } else {
                String out = "";
                for (char ch : res) {
                    out = out + ch;
                }
                return out;
            }
        } else if (edL > stL) {
            for (int i = min; i < edL; i++) {
                if (status == 0) {
                    res.addFirst(ed.get(edL - i-1));
                    status = 0;
                    continue;
                } else {
                    if (ed.get(edL - i-1).equals('1')) {
                        res.addFirst('0');
                        status = 1;
                        continue;
                    } else {
                        res.addFirst('1');
                        status = 0;
                        continue;
                    }
                }
            }
            if (status == 1) {
                res.addFirst('1');
            }
            String out = "";
            for (char ch : res) {
                out = out + ch;
            }
            return out;
        } else {
            for (int i = min; i < stL; i++) {
                if (status == 0) {
                    res.addFirst(st.get(stL - i-1));
                    status = 0;
                    continue;
                } else {
                    if (st.get(stL - i - 1).equals('1')) {
                        res.addFirst('0');
                        status = 1;
                        continue;
                    } else {
                        res.addFirst('1');
                        status = 0;
                        continue;
                    }
                }
            }
            if (status == 1) {
                res.addFirst('1');
            }
            String out = "";
            for (char ch : res) {
                out = out + ch;
            }
            return out;
        }
    }
}

3、最长公共前缀 （Longest Common Prefix）

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:所有输入只包含小写字母 a-z 。

方法一：水平扫描，先对比前两个字符串的前缀，以此前缀对后续字符串进行匹配。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++)
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }        
        return prefix;
    }
}

方法二：暴力匹配，一个一个比

class Solution {
    public String longestCommonPrefix(String[] strs) {
//        定义存在的最长公共字符串的长度
        int Max = 0;
        if (strs.length == 0) {
            return "";
        }
//        定义输入的字符串数组中最短的字符串的长度,初始假设为1000
        int minStr = 1000;
        for (String string : strs) {
            if (string.length() < minStr) {
                minStr = string.length();
            }
        }
//        输入字符串数组的总字符串个数
        int num = strs.length;
        int i = 0;
        LOOP:
        for (; i < minStr; i++) {
            for (int j = 0; j < num; j++) {
                for (int k = j + 1; k < num; k++) {
                    if (strs[j].charAt(i) != strs[k].charAt(i)) {
                        break LOOP;
                    }
                }
            }
        }
        if (i == 0) {
            return "";
        } else {
            return strs[0].substring(0, i);
        }
    }
}