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.

Difficulty: interview

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):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         
         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):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         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):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         
         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):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         dic ={}
         list = []
         list2 = []
         number = 0
         # set a dictionary, 1~26 related a~z
         for letter in string.ascii_lowercase:
                 dic[letter] = number + 1
                 number = number + 1
         # calculate the difference between the two letter, if the target over the letter, put it into list, otherwise put it into list2
         for element in letters:
             if dic[element] > dic[target]:
                 list.append(dic[element] - dic[target])
             else:
                 list2.append(dic[element])
         # find the difference and calculate the nearest letter
         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):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         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):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         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):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         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):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         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):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         for char in letters:
             if char>target: return char
         return letters[0]

class Solution:
     def nextGreatestLetter(self, letters, target):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         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]

from string import ascii_lowercase as al
 class Solution:
     def nextGreatestLetter(self, letters, target):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         index = ord(target) - 96
         s = set(letters)
         i = index
         for i in range(index+1, index + 1 + 26 + 1):
             if chr((i-1) % 26 + 96 + 1) in s:
                 return chr((i-1) % 26 + 96 + 1)
         
         

from string import ascii_lowercase as al
 class Solution:
     def nextGreatestLetter(self, letters, target):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         index = ord(target) - 96
         s = set(letters)
         i = index
         for i in range(index+1, index + 1 + 26 + 1):
             if chr((i-1) % 26 + 96 + 1) in s:
                 return chr((i-1) % 26 + 96 + 1)
         
         

class Solution:
     def nextGreatestLetter(self, letters, target):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         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):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         a=[]
         s=0
         for i in range(0, len(letters)):
             s=a.append(ord(letters[i])-ord(target))
         #return a
         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]
         #return letters[a.index(min)]


class Solution:
     def nextGreatestLetter(self, letters, target):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         if letters[-1] < target:
             return letters[0]    
         
         for letter in letters:
             if letter > target:
                 return letter
         return letters[0] 

class Solution:
     def nextGreatestLetter(self, letters, target):
         """
         :type letters: List[str]
         :type target: str
         :rtype: str
         """
         for c in letters:
             if c > target:
                 return c
         return letters[0]