Find index of the first occurrence in a string

-

 28. Find the Index of the First Occurrence in a String

Easy

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

 

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

 

Constraints:

  • 1 <= haystack.length, needle.length <= 104
  • haystack and needle consist of only lowercase English characters.
My Python:
  • 1
class Solution:
def strStr(self, haystack: str, needle: str) -> int: return haystack.find(needle)
  • 2
class Solution: def strStr(self, haystack: str, needle: str) -> int: for i in range(len(haystack)): if haystack[i]==needle[0]: state=True while state: a=i for j in range(len(needle)): try: if haystack[a]!=needle[j]: state=False break except IndexError: return -1 a+=1 print(i,a) if state: return i return -1

OTHER code:
  • -
class Solution: def strStr(self, haystack: str, needle: str) -> int: if len(needle) == 0: return 0 elif needle not in haystack: return -1 else: return len(haystack.split(needle)[0])






Rabin Karp algo(used in this solution)

  • Rabin Karp, built-in hash, constant time (tested)

def strStr(self, haystack, needle):
	n, h = len(needle), len(haystack)
	hash_n = hash(needle)
	for i in range(h-n+1):
		if hash(haystack[i:i+n]) == hash_n:
			return i
	return -1

  •  Rabin Karp, numeral base for both uppercase and lowercase letters, constant time
def strStr(self, haystack, needle):
	def f(c):
		return ord(c)-ord('A')

	n, h, d, m = len(needle), len(haystack), ord('z')-ord('A')+1, sys.maxint 
	if n > h: return -1
	nd, hash_n, hash_h = d**(n-1), 0, 0   
	for i in range(n):
		hash_n = (d*hash_n+f(needle[i]))%m
		hash_h = (d*hash_h+f(haystack[i]))%m            
	if hash_n == hash_h: return 0        
	for i in range(1, h-n+1):
		hash_h = (d*(hash_h-f(haystack[i-1])*nd)+f(haystack[i+n-1]))%m    # e.g. 10*(1234-1*10**3)+5=2345
		if hash_n == hash_h: return i
return -1  

def strStr(self, haystack, needle):
	n, h = len(needle), len(haystack)
	i, j, nxt = 1, 0, [-1]+[0]*n
	while i < n:                                # calculate next array
		if j == -1 or needle[i] == needle[j]:   
			i += 1
			j += 1
			nxt[i] = j
		else:
			j = nxt[j]
	i = j = 0
	while i < h and j < n:
		if j == -1 or haystack[i] == needle[j]:
			i += 1
			j += 1
		else:
			j = nxt[j]
	return i-j if j == n else -1

Comments

Post a Comment

Popular posts from this blog

-
Image
from tkinter import * from PIL import ImageTk , Image from sqlite3 import * from tkinter import ttk from tkinter import messagebox import time def create ():     global BILL_N , BILL_A , BILL_A_DUE , BILL_UNITS     conn = connect ( 'database.db' ) #     c = conn . cursor ()         # c.execute('''CREATE TABLE K_BILL (account_number integer PRIMARY KEY,     #  name text,     #  units integer,     #  amount_due integer,         #  amount integer)''')             # c.execute(''' INSERT INTO K_Bill VALUES (4902233658724, 'SAMIULLAH', 800 , 20267,800*13)''')     # c.execute(''' INSERT INTO K_Bill VALUES (3769186408275, 'Ali', 25000, 25267,436*13)''')     # c.execute(''' INSERT INTO K_Bill VALUES (9863867106183, 'Faez', 22000, 22567,658*13)''')     c . execute ( ''' UPDATE K_BILL set units=436 wh...
Read more
-
Image
from tkinter import * from PIL import ImageTk , Image from sqlite3 import * from tkinter import ttk from tkinter import messagebox import time # Save updated record def update_record ():     # Grab record number     selected = my_tree . focus ()     # Save new data         my_tree . item ( selected , text = "" , values =( upd_id , items_entry . get (), address_entry . get (), Email_entry . get (), Ph_No_entry . get (), Price_entry . get ()))     #update database     conn = connect ( 'database.db' )     c = conn . cursor ()     c . execute ( '''UPDATE CHECKOUT SET items=?, address=?, email=?, ph_No=?, price=? WHERE id=?''' ,               (( items_entry . get (), address_entry . get (), Email_entry . get (), Ph_No_entry . get (), Price_entry . get (), id ,)))         conn . commit ()     conn . close ()     ...
Read more
-
20. Valid Parentheses Easy 18.3K 1K Companies Given a string  s  containing just the characters  '(' ,  ')' ,  '{' ,  '}' ,  '['  and  ']' , determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.   Example 1: Input: s = "()" Output: true Example 2: Input: s = "()[]{}" Output: true Example 3: Input: s = "(]" Output: false   Constraints: 1 <= s.length <= 10 4 s  consists of parentheses only  '()[]{}' . My code: class Solution: def isValid(self, s: str) -> bool: a='([{' b=')]}' c=[] for i in s: if i in a and s.count(i)!=s.count(b[a.find(i)]):#checks if no.of opening element==no of closing element print(i,b[...
Read more