Leetcode(28) Implement strStr()

发表于 | 更新于 | 分类于

Description:

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

Example 1:

Input: haystack = “hello”, needle = “ll”

Output: 2

Example 2:

Input: haystack = “aaaaa”, needle = “bba”

Output: -1

解法：

首先做特别判断，如果needle的长度大于haystack，不可能匹配，返回-1，如果needle为空，返回0。然后我们开始遍历母字符串，我们并不需要遍历整个母字符串，而是遍历到剩下的长度和子字符串相等的位置即可，这样可以提高运算效率。然后对于每一个字符，我们都遍历一遍子字符串，一个一个字符的对应比较，如果对应位置有不等的，则跳出循环，如果一直都没有跳出循环，则说明子字符串出现了，则返回起始位置即可，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        p = 0;
        q = 0;
        if(len(needle)>len(haystack)):
            return -1;
        if(len(needle) == 0):
            return 0;
        while(p<len(haystack)-len(needle)+1):
            if(haystack[p] == needle[0]):
                q = p;
                flag = 1;
                for x in needle:
                    if(x == haystack[q]):
                        q+=1;
                    else:
                        flag = 0;
                        break;
                if(flag == 1):
                    return p;
            p+=1;
        return -1;

更好写的递归的算法：

判断节点的数量是否构成一组，如果不够，直接返回head，如果够，则将当前组反转，之后的链表变为当前问题的子问题，递归即可，然后再把这两部分连接起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null || k == 1){
            return head;
        }
        ListNode tmp = head;
        int step = 1;
        while(tmp != null && step < k) {
            tmp = tmp.next;
            step++;
        }
        if(tmp == null) {
            return head;
        }
        else{
            ListNode t2 = tmp.next;
            tmp.next = null;
            ListNode newhead =  reverseList(head);
            ListNode newtmp = reverseKGroup(t2,k);
            head.next = newtmp;
            return newhead;
        }
        
    }
    ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        if (head.next == null) {
            return head;
        }
        ListNode res = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }
}