Jamzen的技术博客
0%

LeetCode.实现strStr

发表于 分类于 Valine：

实现 strStr() 函数。给定一个haystack字符串和一个needle字符串，在haystack字符串中找出needle字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

  • 示例 1:
    输入: haystack = “hello”, needle = “ll”
    输出: 2

  • 示例 2:
    输入: haystack = “aaaaa”, needle = “bba”
    输出: -1

解法：

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
object StrMatch {

     def main(args: Array[String]): Unit = {
          println(indexOf("qiaojizhenhello", "iao"))
          println(indexOf("qiaojizhenhello", "zhen"))
          println(indexOf("aaaaa", "bba"))

          println(kmp("qiaojizhenhello", "iao"))
          println(kmp("qiaojizhenhello", "zhen"))
          println(kmp("aaaaa", "bba"))

          println(sunday("qiaojizhenhello", "iao"))
          println(sunday("qiaojizhenhello", "zhen"))
          println(sunday("aaaaa", "bba"))
          println(sunday("ihen", "hen"))
     }

     def indexOf(str: String, sub: String): Int = {
          if (sub == "") {
               return 0
          }
          for (i <- 0 until str.length) {
               breakable(for (j <- 0 until sub.length) {
                    if (str.charAt(i + j) == sub.charAt(j)) {
                         if (j == sub.length - 1) {
                              return i
                         }
                    } else {
                         break()
                    }
               })
          }
          -1
     }

     def kmp(str: String, sub: String): Int = {
          if (sub == "") {
               return 0
          }
          val next: Array[Int] = genNext(sub)
          var i = 0
          var j = 0
          while (i < str.length && j < sub.length) {
               if (j == -1 || str.charAt(i) == sub.charAt(j)) {
                    i += 1
                    j += 1
               } else {
                    j = next(j)
               }
          }

          if (j == sub.length) {
               i - j
          } else {
               -1
          }
     }

     def genNext(str: String): Array[Int] = {
          val next = new Array[Int](str.length)
          val pLen = str.length
          next(0) = -1;
          var k = -1;
          var j = 0;
          while (j < pLen - 1) {
               //p[k]表示前缀，p[j]表示后缀
               if (k == -1 || str.charAt(j) == str.charAt(k)) {
                    k += 1
                    j += 1
                    next(j) = k
                    if (str.charAt(j) != str.charAt(k)) next(j) = k
                    else next(j) = next(k)
               }
               else {
                    k = next(k)
               }
          }
          next
     }

     def bm(str: String, sub: String): Int = {
          if (sub == "") {
               return 0
          }
          //写不出来，呜呜呜呜
          0
     }

     def sunday(str: String, sub: String): Int = {
          if (sub == "") {
               return 0
          }

          val map = scala.collection.mutable.Map[Char, Int]()

          for (k <- sub.length - 1 to 0 by -1) {
               if (!map.contains(sub.charAt(k))) {
                    map += (sub.charAt(k) -> k)
               }
          }

          var i = 0
          var j = 0

          while (i <= str.length - sub.length) {
               j = 0
               while (j <= sub.length) {
                    if (j == sub.length) {
                         return i
                    } else if (str.charAt(i + j) == sub.charAt(j)) {
                         j += 1
                    } else if (i + sub.length >= str.length) {
                         return -1
                    } else {
                         val c = str.charAt(i + sub.length)
                         j = sub.length + 1
                         if (map.contains(c)) {
                              i += sub.length - map.get(c).get
                         } else {
                              i += j
                         }
                    }
               }
          }
          -1
     }
}