2018-04-17 - String

28. Implement strStr()

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

My code

class Solution {
    public static int strStr(String haystack, String needle) {
        int len_stack = haystack.length();
        int len_nd = needle.length();
        char st[] = haystack.toCharArray();
        char nd[] = needle.toCharArray();
        
        if (len_nd == 0) {return 0;}
        for (int i = 0; i < len_stack; i++) {
            if ( st[i] == nd[0]) {
                int k = i;
                for  (int j = 0; j < len_nd && k < len_stack && st[k] == nd[j]; j++) {
                        k++;
                    }
                if (k == i + len_nd) {
                    return i;
                } 
            } 

        }return -1;
    }
}

// another way is to use the needle as a block

• 数据比较
  基本数据类型可以==来判断;
  引用类型用equals()

(字符类型char，布尔类型boolean以及数值类型byte、short、int、long、float、double)

substring, like a window

            if (haystack.substring(i,i+l2).equals(needle)) {
                return i;
            }

More concise one

    public int strStr(String s, String t) {
        if (t.isEmpty()) return 0; // edge case: "",""=>0  "a",""=>0
        for (int i = 0; i <= s.length() - t.length(); i++) {
            for (int j = 0; j < t.length() && s.charAt(i + j) == t.charAt(j); j++)
                if (j == t.length() - 1) return i;
        }
        return -1;
    }

To make sure the substring of haystack long enough to hold the needle string. For example if needle string length is 5 and haystack string length is 10, the possible value for index is from 0 to haystack.length() - t.length()

459. Repeated Substring Pattern

* str.substring(start, end)

slice the substring from start to end.

C++,C#,Java都是比较严格的语言，关键字、变量名严格区分大小写。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        for(int i = len/2; i > 0; i--) {
            if (len % i == 0) {
                String sub_str = s.substring(0, i);
                int supposed_repeated_time = len/i;
                int j = 1;
                for (; j < supposed_repeated_time; j++) {
                    if (!sub_str.equals(s.substring(j*i, i + j*i))) { // Here, the start should change when the j changes! It's the start of the windoe!
                        break;
                    }
                } if (j == supposed_repeated_time) {
                    return true;
                }
            }
        } return false;
        
    }
}

// Q 
// whether the string is constructed only by repeating the substring
// not contain, but all constructed. 

// Main part:
// how to find the smallest part - the substring;
// how to find the length

// Notice that the shortest length of the substring is len/2
// bcoz that the substring should repeat at least once. 

// Notice that: "bb" should return true!

* str.indexOf()

Java中字符串中子串的查找共有四种方法，如下：
1、int indexOf(String str) ：返回第一次出现的指定子字符串在此字符串中的索引。
2、int indexOf(String str, int startIndex)：从指定的索引处开始，返回第一次出现的指定子字符串在此字符串中的索引。
3、int lastIndexOf(String str) ：返回在此字符串中最右边出现的指定子字符串的索引。
4、int lastIndexOf(String str, int startIndex) ：从指定的索引处开始向后搜索，返回在此字符串中最后一次出现的指定子字符串的索引。

public boolean repeatedSubstringPattern(String str) {
        for(int i=str.length()/2;i>=1;i--){
            if(str.length()%i==0){
                int j=i;
                String sub=str.substring(0,j);
                while(str.indexOf(sub,j)==j)j+=i;
                if(j==str.length())return true;
            }
        }
        return false;
    }

214. Shortest Palindrome

StringBuilder, StringBuffer, String

To create a StringBuilder from a String simply: StringBuilder sb = new StringBuilder("MyString"); String s = sb.toString();. But as was said StringBuilder and StringBuffer are different. Take a look here for more information on StringBuilder and StringBuffer.

214是一道我写跪了的题

• Brute Force
• 找最长回文前缀。
  再在字符串的头部加上除去最长回文前缀之外的子字符串的翻转即为所求。
  https://blog.csdn.net/magicbean2/article/details/73483311
  这里也有两种方法

题外话

昨天晚上拿了一个Summer Intern 的offer，一兴奋就忘记刷题了，罪过罪过。今天补上～
看到offer上写的“Software Engineer Intern”有点小激动。虽然只是一家很小的Startup，但是感觉自己又有了选择，也好像看到了未来。现在说这些话实在为时过早，但是在低迷的时候也会发现机遇。
目前BAT都还没有面试，但是阿里的面试已经越好了，其他的估计也能有机会吧。希望自己不要因为自己的不努力而错过，而遗憾。

// 阿里电面要考编程，自己这两天要多刷一些题了！最好大致所有的类别都能过一下。
// 同时机器学习的面试题不能停止。加油！
// 今天上手了一下eclipse