LeetCode(11) -- 459, 771

P459. Repeated Substring Pattern (Easy)

给一个字符串，判断它是否是由多个子字符串重复而成的。只有小写英文字母。

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

我的思路

如何找出开始重复的点？如果发现跟第一个字母相同，就开始往后对比，直到完全相同，说明找到了一个周期，如果遇到任何一个不一样，就要再看是否跟第一个字母一样。

这个算法是错的。因为如果是”abcabcef”作为一周期，到第二个c时，我以为找到了一个周期，实际上我应该更新第二周期的起始点，因为刚才的周期是错误的。

我的代码

写了半天总有bug，放弃。

讨论区

int l = str.length();
	for(int i=l/2;i>=1;i--) {
		if(l%i==0) {
			int m = l/i;
			String subS = str.substring(0,i);
			StringBuilder sb = new StringBuilder();
			for(int j=0;j<m;j++) {
				sb.append(subS);
			}
			if(sb.toString().equals(str)) return true;
		}
	}
	return false;

66%

最优解

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        if (len <= 1) {
            return false;
        }
        char last = s.charAt(len - 1);
        int val = s.lastIndexOf(last, len / 2 - 1) + 1;
        while (val > 0) {
            if (len % val == 0) {
                String pat = s.substring(0, val);
                boolean res = true;
                for (int i = val; i < len; i += val) {
                    if (!s.substring(i, i + val).equals(pat)) {
                        res = false;
                        break;
                    }
                }
                if (res) {
                    return res;
                }
            }
            val = s.lastIndexOf(last, val - 2) + 1;
        }
        return false;
    }
}

暂时无法理解，留个坑，将来有空再看。。。

P771. Jewels and Stones (Easy)

一个字符串J记录所有代表珠宝的字母，第二个字符串S记录我手中所有的石头，包含珠宝，因为珠宝也是石头的一种。 问我手中的石头中有多少个是珠宝。

Input: J = "aA", S = "aAAbbbb"
Output: 3

我的思路

先通过J字符串，用一个布尔型数组记录下哪些字母是珠宝； 再挨个看S里面有多少是属于珠宝的即可。

我的代码

class Solution {
    public int numJewelsInStones(String J, String S) {
        int counter = 0;
        boolean[] letters = new boolean[58];
        for (int i = 0; i < J.length(); i++) {
            letters[J.charAt(i) - 'A'] = true;
        }
        for (int i = 0; i < S.length(); i++) {
            if (letters[S.charAt(i) - 'A']) {
                counter++;
            }
        }
        return counter;
    }
}

100%

最优解

class Solution {
    public int numJewelsInStones(String J, String S) {
        int sum = 0;
        for(char c: S.toCharArray()){
            if(J.indexOf(c) >= 0)
                sum++;
        }
        return sum;
    }
}

这个答案虽然很短，但时间复杂度其实是m * n。indexOf方法是需要字符串整体搜索的。我觉得不好。