双非本科准备秋招（11.2）—— 力扣字符串

今天学习状态不佳，JVM也没学，水一水字符串的题，休息休息再战。

1、LCR 122. 路径加密

emmmm，替换一下就行了，也没啥可讲的。

class Solution {
    public String pathEncryption(String path) {
        return path.replace(".", " ");
    }
}

2、LCR 182. 动态口令

就是把字符串截取一下，把前半部分放到后半部分。

class Solution {
    public String dynamicPassword(String password, int target) {
        String a = password.substring(0, target);
        String b = password.substring(target);
        return b+a;
    }
}

3、28. 找出字符串中第一个匹配项的下标

哈哈哈哈哈哈哈，直接一个indexOf。

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

 其实这个题考察KMP算法（模板），这个东西挺麻烦的，看了半天，最后看到这个老哥讲的非常好，属于非常细致了，推荐一下：

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

本题代码如下：

class Solution {
    public int strStr(String haystack, String needle) {
        char[] s = haystack.toCharArray();
        char[] p = needle.toCharArray();
        int[] _next = new int[p.length+1];
        getNext(p, _next);

        for(int i = 0, j = 0; i < s.length; i++){
            while(j > 0 && s[i] != p[j]) j = _next[j];
            if(s[i] == p[j]) j++;
            if(j == p.length){
                return i-j+1;
            }
        }
        return -1;
    }

    void getNext(char[] p, int[] _next){
            for(int j = 2, i = 0; j <= p.length; j++){
                while(i > 0 && p[j-1] != p[i]) i = _next[i];
                if(p[j-1] == p[i]) i++;
                _next[j] = i;
            }
        }
}

4、459. 重复的子字符串

如果s是由重复的子字符串构成，那么循环移动s中的每个元素，一定能得到自己。

比如s=abc，那么abc的移动情况，会包含在abcabc中，abc(abc)->a(bca)bc->ab(cab)c

再比如s=abcabc，那么abcabc的移动情况，会包含在abcabcabcabc中，abcabc(abcabc)->a(bcabca)bcabc->ab(cabcab)cabc->abc(abcabc)abc······

可以看到，掐头去尾后，如果s+s中包含s，那么就说明s是由重复的子字符串构成。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String t = s+s;
        return t.substring(1, t.length()-1).contains(s);
    }
}