算法笔记|Day8字符串II

算法笔记|Day8字符串II

• ☆☆☆☆☆leetcode 151.翻转字符串里的单词
• • 题目分析
  • 代码
• ☆☆☆☆kamacoder 55. 右旋字符串（待补充）
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 28. 实现 strStr()
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 459.重复的子字符串
• • 题目分析
  • 代码

☆☆☆☆☆leetcode 151.翻转字符串里的单词

题目链接：leetcode 151.翻转字符串里的单词

题目分析

1.此题需要完成三个步骤：移除多余空格，将整个字符串反转，将每个单词反转；
2.移除空格需要注意：首尾的空格应删掉，每两个单词之间要保留一个空格，同时为了保证删去多余的元素，应该对数组重新resize；
3.时间复杂度为O(n)，空间复杂度为O(1)。

代码

class Solution {
    public String reverseWords(String s) {
        char ch[]=s.toCharArray();
        ch=removeSpaces(ch);
        reverse(ch,0,ch.length-1);
        reverseEachWord(ch);
        return new String(ch);
    }

    public char[] removeSpaces(char[] ch){
        int slow=0,fast=0;
        for(;fast<ch.length;fast++){
            if(ch[fast]!=' '){
                if(slow!=0){
                    ch[slow]=' ';
                    slow++;
                }
                while(fast<ch.length&&ch[fast]!=' '){
                    ch[slow]=ch[fast];
                    slow++;
                    fast++;
                }
            }
        }
        char newch[]=new char[slow];//相当于resize
        for(int index=0;index<slow;index++){
            newch[index]=ch[index];
        }
        return newch;
    }
    
    public void reverseEachWord(char[] ch){
        int left=0,right=0;
        for(;right<=ch.length;right++){
            if(right==ch.length||ch[right]==' '){
                reverse(ch,left,right-1);
                left=right+1;
            }
        }
    }
    
    public void reverse(char[] ch,int left,int right){
        while(left<right){
            char temp=ch[left];
            ch[left]=ch[right];
            ch[right]=temp;
            left++;
            right--;
        }
    }
}

☆☆☆☆kamacoder 55. 右旋字符串（待补充）

题目链接：kamacoder 55. 右旋字符串

题目分析

代码

☆☆☆☆☆leetcode 28. 实现 strStr()

题目链接：leetcode 28. 实现 strStr()

题目分析

1.本题为KMP经典题目，其思想为：当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配；
2.前缀表（next数组）是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配，其第i个元素为记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀；
3.时间复杂度为O(n + m)，空间复杂度为O(m)。

代码

class Solution {
    public int strStr(String haystack, String needle) {
        int next[]=new int[needle.length()];
        getNext(needle,next);
        int j=0;
        for(int i=0;i<haystack.length();i++){
            while(j>0&&needle.charAt(j)!=haystack.charAt(i))
                j=next[j-1];
            if(needle.charAt(j)==haystack.charAt(i))
                j++;
            if(j==needle.length())
                return i-needle.length()+1;        
        }
        return -1;
    }

    private void getNext(String s,int[] next){
        int j=0;
        next[0]=0;
        for(int i=1;i<s.length();i++){
            while(j>0&&s.charAt(j)!=s.charAt(i))
                j=next[j-1];
            if(s.charAt(j)==s.charAt(i))
                j++;
            next[i]=j;
        }
    }
}

☆☆☆☆☆leetcode 459.重复的子字符串

题目链接：leetcode 459.重复的子字符串

题目分析

1.本题可以用字符串匹配的方法，判断s+s拼接的字符串中间是否出现一个s的的时候，注意需要刨除s+s的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s，此方法可以用到库函数，但时间复杂度较高；
2.本题还可以考虑KMP方法，数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环，即返回true，否则返回false；
3.时间复杂度为O(n)，空间复杂度为O(n)。

代码

1.字符串匹配的方法
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String t = s + s;  
        t = t.substring(1, t.length() - 1); // 掐头去尾  
        if (t.contains(s)) 
            return true;  
        return false;  
    }
}

2.KMP方法
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len=s.length();
        int next[]=new int[len];
        int j=0;
        next[0]=0;
        for(int i=1;i<s.length();i++){
            while(j>0&&s.charAt(j)!=s.charAt(i))
                j=next[j-1];
            if(s.charAt(j)==s.charAt(i))
                j++;
            next[i]=j;
        }
        if(next[len-1]>0&&len%(len-next[len-1])==0)
            return true;
        return false;
    }
}