算法第八天|字符串篇

右旋字符串

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        String str = scanner.next();
        String value = getStr(num, str);
        System.out.println(value);
    }

    private static String getStr(int num, String str) {
        if (num >= str.length()) {
            return str;
        }

        int left = str.length() - num;

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < left; i++) {
            stringBuilder.append(str.charAt(i));
        }
        StringBuilder newStringBuilder = new StringBuilder();
        for (int i = left; i < str.length(); i++) {
            newStringBuilder.append(str.charAt(i));
        }
        newStringBuilder.append(stringBuilder);

        return new String(newStringBuilder);
    }
}

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

 public int strStr(String haystack, String needle) {
        int i = haystack.indexOf(needle);
        return i;
    }

    public int strStr2(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return -1;
        }

        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            int x = 0;
            int tempI = i;
            while (x < needle.length() && haystack.charAt(tempI) == needle.charAt(x)) {
                tempI++;
                x++;
            }
            if (x == needle.length()) {
                return i;
            }
        }
        return -1;
    }

自己的算法复杂度是O(m*n),应该使用KMP算法求解，不过今天时间紧，明天加上。

459. 重复的子字符串

  public static boolean repeatedSubstringPattern(String s) {

        StringBuilder stringBuilder = new StringBuilder();
        StringBuilder stringBuilder2 = new StringBuilder(s.length());
        for (int i = 0; i < s.length() - 1; i++) { // 因为是字串，所以减一
            stringBuilder.append(s.charAt(i));
            if (s.length() % stringBuilder.length() == 0) { // 要求字串重复M倍组成s，那么余数必然等于0
                while (stringBuilder2.length() < s.length()) {
                    stringBuilder2.append(stringBuilder);
                }
                if (new String(stringBuilder2).equals(s)) {
                    return true;
                }
                stringBuilder2 = new StringBuilder(s.length());
            }
        }
        return false;
    }

肯定有简化的方法，这样的时间复杂度有点高，O(nlogn)