Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix).
It will return the word with given prefix and suffix with maximum weight.  If no word exists, return -1.


Examples:

Input:
WordFilter(["apple"])
WordFilter.f("a", "e") // returns 0
WordFilter.f("b", "") // returns -1


Note:

words has length in range [1, 15000].
For each test case, up to words.length queries WordFilter.f may be made.
words[i] has length in range [1, 10].
prefix, suffix have lengths in range [0, 10].
words[i] and prefix, suffix queries consist of lowercase letters only.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: class WordFilter:
    def __init__(self, words: List[str]):
    def f(self, prefix: str, suffix: str) -> int:
# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(prefix,suffix)

Solutions:
class Solution:

	def nextGreatestLetter(self, letters, target):
		if ord(letters[-1]) <= ord(target):
			return letters[0]
		li = 0
		ri = len(letters) - 1
		while li <= ri:
			if li == ri:
				return letters[li]
			mi = li + (ri - li) // 2
			if ord(letters[mi]) > ord(target):
				ri = mi
			else:
				li = mi + 1


class Solution:

	def nextGreatestLetter(self, letters, target):
		st = 0
		ed = len(letters) - 1
		if target < letters[0] or target > letters[-1]:
			return letters[0]
		while st <= ed:
			mid = st + (ed - st) // 2
			if letters[mid - 1] < target and letters[mid] > target:
				return letters[mid]
			if letters[mid] == target:
				ans = letters[0]
				i = mid
				while i < len(letters):
					if letters[i] != target:
						return letters[i]
					i += 1
				return ans
			if letters[mid] < target:
				st = mid + 1
			else:
				ed = mid - 1


class Solution:

	def nextGreatestLetter(self, letters, target):
		for idx in range(len(letters)):
			c = letters[idx]
			if c > target:
				return c
			if idx == len(letters) - 1:
				return letters[0]


class Solution:

	def nextGreatestLetter(self, letters, target):
		dic = {}
		list = []
		list2 = []
		number = 0
		for letter in string.ascii_lowercase:
			dic[letter] = number + 1
			number = number + 1
		for element in letters:
			if dic[element] > dic[target]:
				list.append(dic[element] - dic[target])
			else:
				list2.append(dic[element])
		if list != []:
			minnum = min(list)
			return string.ascii_lowercase[dic[target] + minnum - 1]
		else:
			minnum = min(list2)
			return string.ascii_lowercase[minnum - 1]


class Solution:

	def nextGreatestLetter(self, letters, target):
		res = ''
		if target == 'z':
			target = '0'
		large = 'z'
		found = False
		for i in range(len(letters)):
			if letters[i] > target and (not found):
				found = True
				res = letters[i]
			elif found and (not res < letters[i]):
				res = letters[i]
			elif letters[i] < large:
				large = letters[i]
		return large if len(res) == 0 else res


class Solution:

	def nextGreatestLetter(self, letters, target):
		curr_small = None
		for letter in letters:
			if letter > target:
				if curr_small == None or curr_small > letter:
					curr_small = letter
		if curr_small:
			return curr_small
		else:
			return letters[0]


class Solution:

	def nextGreatestLetter(self, letters, target):
		tmp = list(map(ord, letters))
		d = [x - y for (x, y) in zip(tmp, [ord(target)] * len(letters))]
		for i in range(len(d)):
			if d[i] <= 0:
				d[i] = 26 + d[i]
		return letters[d.index(min(d))]


class Solution:

	def nextGreatestLetter(self, letters, target):
		(lo, hi) = (0, len(letters))
		while lo < hi:
			mid = lo + (hi - lo) // 2
			if letters[mid] <= target:
				lo = mid + 1
			else:
				hi = mid
		return letters[lo % len(letters)]


class Solution:

	def nextGreatestLetter(self, letters, target):
		for char in letters:
			if char > target:
				return char
		return letters[0]


class Solution:

	def nextGreatestLetter(self, letters, target):
		if letters is None or len(letters) == 0:
			return None
		(start, end) = (0, len(letters) - 1)
		while start + 1 < end:
			mid = start + (end - start) // 2
			if letters[mid] <= target:
				start = mid
			else:
				end = mid
		if letters[start] > target:
			return letters[start]
		elif letters[end] > target:
			return letters[end]
		else:
			return letters[0]


class Solution:

	def nextGreatestLetter(self, letters, target):
		minL = 'z'
		result = 'z'
		wrap = True
		for l in letters:
			minL = min(minL, l)
			if l > target:
				wrap = False
				result = min(result, l)
		if not wrap:
			return result
		else:
			return minL


class Solution:

	def nextGreatestLetter(self, letters, target):
		a = []
		s = 0
		for i in range(0, len(letters)):
			s = a.append(ord(letters[i]) - ord(target))
		min = 100
		for i in range(0, len(a) - 1):
			if ord(letters[i]) <= ord(target) and ord(letters[i + 1]) > ord(target):
				return letters[i + 1]
		if ord(letters[0]) - ord(target) == 0:
			return letters[1]
		else:
			return letters[0]


class Solution:

	def nextGreatestLetter(self, letters, target):
		if letters[-1] < target:
			return letters[0]
		for letter in letters:
			if letter > target:
				return letter
		return letters[0]