pie.py

import collections
from helperlc import print_l
from helperlc import print_tree
from helperlc import TreeNode
from helperlc import Node
from helperlc import ListNode
from helperlc import get_tree_node_levelorder
from typing import List
import timeit


def main():
    sol = Solution()  # None
    arg = [1, None, 5, 2]
    root = get_tree_node_levelorder(arg)
    arg1 = "segmentation"
    arg2 = ["bbbbbxbbbbb1"]
    # t = timeit.timeit("sol = Solution(); rs = sol.solveNQueens(4)", number=5 ,
    # setup="from pie import Solution") print(t)
    rs = sol.generateAbbreviations(arg1)
    # print_tree(root)
    print(rs)
    # print(len(rs))
# next Greater element, net permutation, permutation, combination
# for i, num in enumerate(nums[1:], 1):
# https://zxi.mytechroad.com/blog/two-pointers/leetcode-1385-find-the-distance-value-between-two-arrays/
# sum(all(abs(x - y) > d for y in arr2) for x in arr1)
# [ch if not ch.isdigit() else '*' * int(ch) for ch in abbr]
# backtracking, bisect, min - priority queue
class Solution:


    def generateAbbreviations(self, word):
        def abbr(word):
            if not word: return []
            ls = []
            wl = len(word)
            for i in range(wl):
                aword = word
                k = 0
                while k + i < len(aword):
                    aword = aword[:k] + str(i + 1) + aword[k + i + 1:]
                    ls.append(aword)
                    k += 1
                    if i >= 9:
                        k += 1
                    if aword[:2] == "1e":
                        print(aword[:k], aword[k:], k)
                    if len(aword) >= k:
                        temp = abbr(aword[k:])
                        rs = []
                        if aword[:2] == "1e":
                            print(":", aword[:k], aword[k:])
                        for tword in temp:
                            if not tword.isdigit() and not tword[0].isdigit():
                                rs.append(aword[:k] + tword)
                        ls += rs
                    aword = word
            return ls
        return abbr(word) + [word]

    def wordsAbbreviation(self, dict):
        temp = {}
        for word in dict:
            if len(word) > 3:
                key = word[0] + str(len(word) -2) + word[-1]
            else:
                key = word
            temp.setdefault(key, []).append(word)

        def conflict_resolution(dic, ls):
            size = len(ls[0]) - 2
            front = -1
            for i in range(1, size):
                num = size - i
                stemp = set()
                for word in ls:
                    abbr = word[:i] + str(num + 1) + word[-1]
                    stemp.add(abbr)
                if len(stemp) == len(ls):
                    front = i
                    break
            for word in ls:
                if front == -1:
                    dic[word] = word
                else:
                    abbr = word[:front] + str(size - front + 1) + word[-1]
                    dic[word] = abbr

        dic = {}
        for key, val in temp.items():
            if len(val) > 1:
                conflict_resolution(dic, val)
            else:
                dic[val[0]] = key
        return [dic[word] for word in dict]

    def partition(seq):
        pi, seq = seq[0], seq[1:]  # Pick and remove the pivot
        lo = [x for x in seq if x <= pi]  # All the small elements
        hi = [x for x in seq if x > pi]  # All the large ones
        return lo, pi, hi  # pi is "in the right place"

    def select(seq, k):
        lo, pi, hi = partition(seq)  # [<= pi], pi, [>pi]
        m = len(lo)
        if m == k:
            return pi  # We found the kth smallest
        elif m < k:  # Too far to the left
            return select(hi, k - m - 1)  # Remember to adjust k
        else:  # Too far to the right
            return select(lo, k)  # Just use original k here


    def minAbbreviation(self, target, dictionary):

        def abbr(word):
            if not word: return []
            ls = []
            wl = len(word)
            for i in range(wl):
                aword = word
                k = 0
                while k + i < len(aword):
                    aword = aword[:k] + str(i + 1) + aword[k + i + 1:]
                    ls.append(aword)
                    k += 1
                    if len(aword) - 1 - i >= k:
                        temp = abbr(aword[k:])
                        rs = []
                        # print(aword[:k], aword[k:], temp )
                        for tword in temp:
                            if not tword.isdigit() and not tword[0].isdigit():
                                rs.append(aword[:k] + tword)
                        ls += rs
                    aword = word
            return ls

        targets = abbr(target) + [target]
        targets.sort(key=len)
        for small in targets:
            if not sum(self.validWordAbbreviation(word, small) for word in dictionary):
                return small
        return dics

    def minAbbreviation_(self, target, dictionary):

        def abbr(word):
            if not word: return []
            ls = []
            wl = len(word)
            for i in range(wl):
                aword = word
                k = 0
                while k + i < len(aword):
                    aword = aword[:k] + str(i + 1) + aword[k + i + 1:]
                    ls.append(aword)
                    k += 1
                    if len(aword) - 1 - i >= k:
                        temp = abbr(aword[k:])
                        rs = []
                        for tword in temp:
                            if not tword.isdigit() and not tword[0].isdigit():
                                rs.append(aword[:k] + tword)
                        ls += rs
                    aword = word
            return ls

        targets = abbr(target) + [target]
        targets.sort(key=len)
        dics = []
        for dword in dictionary:
            dics += abbr(dword) + [dword]
        dics = set(dics)
        for small in targets:
            if small not in dics:
                return small
        return dics

    def validWordAbbreviation(self, word, abbr):
        i, j = 0, 0
        wl = len(word)
        while i < len(abbr):
            num = ""
            while i < len(abbr) and abbr[i].isdigit():
                if not num and abbr[i] == '0':
                    break
                num += abbr[i]
                i += 1
            if num:
                j += int(num)
            else:
                if j < wl and abbr[i] != word[j]:
                    return False
                i += 1
                j += 1
        return wl == j

    def wordSquares(self, words):
        if not words: return words
        from collections import defaultdict
        ans = []
        n = len(words[0])
        dic = defaultdict(list)
        for word in words:
            for i in range(1, n):
                dic[word[:i]].append(word)

        def backtrack(arr):
            length = len(arr)
            if length == n:
                ans.append(arr)
            else:
                key = ''
                for word in arr:
                    key += word[length]
                if dic[key]:
                    for word in dic[key]:
                        backtrack(arr + [word])

        for word in words:
            backtrack([word])
        return ans

    def wordSquares_(self, words: List[str]):
        size = len(words[0])
        if size == 1: return words
        res = []

        def check(ls):
            tsize = len(ls) - 1
            if tsize < 1:
                return True
            for row in range(tsize):
                if ls[row][tsize] != ls[tsize][row]:
                    return False
            return True

        def backtracking(ls):
            tsize = len(ls)
            if not check(ls):
                return

            if tsize == size:
                nonlocal res
                res.append(list(ls))
                return
            for word in words:
                ls.append(word)
                backtracking(ls)
                ls.pop()

        backtracking([])
        return res

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordDict = set(wordDict)
        memo = {}

        def backtracking(input):
            if not input: return True
            nonlocal memo
            if input in wordDict: return True
            for pos in range(len(input), -1, -1):
                lefts, right = input[:pos], input[pos:]
                if right in wordDict:
                    flag = backtracking(lefts)
                    if flag: return True
            memo[input] = False
            return False

        return backtracking(s)

    def wordBreak_(self, s: str, wordDict: List[str]) -> List[str]:
        wordDict = set(wordDict)
        memo = {}

        def backtracking(input):
            if not input: return []
            nonlocal memo
            if input in memo: return memo[input]
            res = []
            if input in wordDict:
                res.append(input)
            for pos in range(len(input)):
                lefts, right = input[:pos], input[pos:]
                if right in wordDict:
                    ls = backtracking(lefts)
                    for left in ls:
                        res.append(left + " " + right)
            memo[input] = res
            return res

        return backtracking(s)

    def isMatch(self, s: str, p: str) -> bool:
        memo = {}

        def _isMatch(s: str, p: str) -> bool:
            nonlocal memo
            if (s, p) in memo:
                return memo[(s, p)]
            if not p: return s == ""
            if len(p) >= 2 and p[1] == "*":
                res = _isMatch(s, p[2:]) or \
                      (s != ""
                       and (s[0] == p[0] or '.' == p[0])
                       and _isMatch(s[1:], p))
            else:
                res = s != "" \
                      and (s[0] == p[0] or '.' == p[0]) \
                      and _isMatch(s[1:], p[1:])
            memo[(s, p)] = res
            return res

        return _isMatch(s, p)

    def isMatch___(self, s: str, p: str) -> bool:
        memo = {}

        def isMatch(s: str, p: str) -> bool:
            nonlocal memo
            if (s, p) in memo:
                return memo[(s, p)]
            if not p: return s == ""
            if not s:
                res = p[0] == '*' and isMatch(s, p[1:])
            elif p[0] == "*":
                res = isMatch(s[1:], p) or isMatch(s, p[1:])
            else:
                res = (s[0] == p[0] or '?' == p[0]) \
                      and isMatch(s[1:], p[1:])
            memo[(s, p)] = res
            return res

        return isMatch(s, p)

    def isMatch__(self, s: str, p: str) -> bool:
        if not p: return s == ""
        if not s:
            return p[0] == '*' and self.isMatch(s, p[1:])
        if p[0] == "*":
            return self.isMatch(s[1:], p) or self.isMatch(s, p[1:])
        else:
            return (s[0] == p[0] or '?' == p[0]) \
                   and self.isMatch(s[1:], p[1:])

    def isMatch_(self, s: str, p: str) -> bool:
        if not p: return s == ""
        if len(p) >= 2 and p[1] == "*":
            return self.isMatch(s, p[2:]) or \
                   (s != ""
                    and (s[0] == p[0] or '.' == p[0])
                    and self.isMatch(s[1:], p))
        else:
            return s != "" \
                   and (s[0] == p[0] or '.' == p[0]) \
                   and self.isMatch(s[1:], p[1:])

    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        if endWord not in wordList:
            return []

        wordList = set(wordList)  # convert to set for O(1) lookup
        left, right = {beginWord}, {endWord}  # frontiers at both ends
        left_parents, right_parents = defaultdict(set), defaultdict(
            set)  # map word to its parent
        swapped = False  # have the frontiers been swapped?

        while left and right and not (
                left & right):  # while both frontiers and no intersection

            if len(right) < len(left):  # swap to expand smaller frontier
                left, right = right, left
                left_parents, right_parents = right_parents, left_parents
                swapped = not swapped

            next_left = defaultdict(set)
            for word in left:
                for char in string.ascii_lowercase:
                    for i in range(len(beginWord)):
                        n = word[:i] + char + word[
                                              i + 1:]  # replace every position with every char
                        if n in wordList and n not in left_parents:  # valid word not been used
                            next_left[n].add(word)

            left_parents.update(next_left)
            left = set(next_left.keys())

        if swapped:  # swap back
            left, right = right, left
            left_parents, right_parents = right_parents, left_parents

        ladders = [[word] for word in
                   left & right]  # start from central intersection
        while ladders and ladders[0][
            0] not in beginWord:  # extend ladders left to start
            ladders = [[p] + l for l in ladders for p in left_parents[l[0]]]
        while ladders and ladders[0][-1] != endWord:  # extend ladders right to end
            ladders = [l + [p] for l in ladders for p in right_parents[l[-1]]]

        return ladders

    def solveNQueens(self, arg: int) -> List[List[str]]:
        sols = []

        def check_slope(sol):
            if not sol:
                return False
            new_q = sol[-1]
            for q in sol[:-1]:
                slope = (q[1] - new_q[1]) / (q[0] - new_q[0])
                if slope == 1 or slope == -1:
                    return True
            return False

        def backtrack(rows, cols, sol):
            nonlocal sols
            print(rows, cols, sol)
            if check_slope(sol):
                return
            if len(sol) == arg:
                ls = []
                for (i, j) in sol:
                    ls.append('.' * j + 'Q' + '.' * (arg - 1 - j))
                sols.append(ls)
                print("solutions : ", sol)
                return

            for row in sorted(rows):
                for col in cols:
                    if sol:
                        if row <= sol[-1][0]:
                            break
                    sol.append((row, col))
                    nrows = set(rows)
                    nrows.remove(row)
                    ncols = set(cols)
                    ncols.remove(col)
                    backtrack(nrows, ncols, sol)
                    sol.pop()

        nums = range(arg)
        rows, cols = set(nums), set(nums)
        backtrack(rows, cols, [])
        return sols

    def solveNQueens_(self, arg: int) -> List[List[str]]:
        sols = []

        def check_slope(sol):
            if not sol:
                return False
            new_q = sol[-1]
            for q in sol[:-1]:
                slope = (q[1] - new_q[1]) / (q[0] - new_q[0])
                if slope == 1 or slope == -1:
                    return True
            return False

        def backtrack(rows, cols, sol):
            nonlocal sols
            if check_slope(sol):
                return
            if len(sol) == arg:
                ls = []
                for (i, j) in sol:
                    ls.append('.' * j + 'Q' + '.' * (arg - 1 - j))
                sols.append(ls)
                return
            for i, row in enumerate(rows):
                for j, col in enumerate(cols):
                    if sol:
                        if i <= sol[-1][0]:
                            break
                    if not row and not col:
                        sol.append((i, j))
                        nrows = list(rows)
                        ncols = list(cols)
                        nrows[i] = 1
                        ncols[j] = 1
                        backtrack(nrows, ncols, sol)
                        sol.pop()

        rows, cols = [0] * arg, [0] * arg
        backtrack(rows, cols, [])
        return sols

    def ladderLengthII(self, beginWord: str, endWord: str, wordList: List[str]):
        ws = set(wordList)
        if endWord not in ws:
            return []
        if beginWord in ws:
            ws.remove(beginWord)
        from collections import deque
        from string import ascii_lowercase
        q = deque()
        q.append(beginWord)
        seen = {}
        level = 1
        rs = []
        dic = {}
        level_dic = {}
        end_word_found = False
        while q and not end_word_found:
            level += 1
            for _ in range(len(q)):
                word = q.popleft()
                temp = []
                for pos in range(len(word)):
                    if word in seen and seen[word] == pos:
                        continue
                    for ch in ascii_lowercase:
                        wls = list(word)
                        wls[pos] = ch
                        new_ch_word = ''.join(wls)
                        if new_ch_word in ws or new_ch_word == endWord:
                            level_dic[new_ch_word] = level + 1
                            temp.append(new_ch_word)
                            if new_ch_word == endWord:
                                end_word_found = True
                            else:
                                ws.remove(new_ch_word)
                                seen[new_ch_word] = pos
                                q.append(new_ch_word)
                        else:
                            if new_ch_word in level_dic \
                                    and level_dic[new_ch_word] == level + 1:
                                temp.append(new_ch_word)
                if temp:
                    dic[word] = temp

        def backtrack(rs, ls, word):
            if word == endWord:
                rs.append(list(ls))
                return
            if word not in dic:
                return
            for next in dic[word]:
                ls.append(next)
                backtrack(rs, ls, next)
                ls.pop()

        backtrack(rs, [beginWord], beginWord)
        return rs

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        ws = set(wordList)
        if endWord not in ws:
            return 0
        from collections import deque
        from string import ascii_lowercase
        q = deque()
        q.append(beginWord)
        seen = {}
        level = 1
        while q:
            level += 1
            for _ in range(len(q)):
                word = q.popleft()
                for pos in range(len(word)):
                    if word in seen and seen[word] == pos:
                        continue
                    for ch in ascii_lowercase:
                        wls = list(word)
                        wls[pos] = ch
                        new_ch_word = ''.join(wls)
                        if new_ch_word == endWord:
                            return level
                        if new_ch_word in ws:
                            ws.remove(new_ch_word)
                            seen[new_ch_word] = pos
                            q.append(new_ch_word)
        return 0

    def ladderLength1(self, beginWord: str, endWord: str,
                      wordList: List[str]) -> int:
        wordSet = set(wordList)
        if endWord not in wordSet:
            return 0
        from string import ascii_lowercase
        front = set()
        front.add(beginWord)
        back = set()
        back.add(endWord)
        level = 0
        ht = {beginWord: -1, endWord: -1}
        while front and back:
            level += 1
            if len(front) > len(back):
                temp = front.copy()
                front = back
                back = temp
            new_front = set()
            print(front, back)
            for _ in range(len(front)):
                each = front.pop()
                for pos in range(len(each)):
                    if ht[each] == pos:
                        continue
                    print(ht)
                    for c in ascii_lowercase:
                        temp = list(each)
                        temp[pos] = c
                        t_word = ''.join(temp)
                        if t_word in back:
                            return level + 1
                        if t_word in wordSet:
                            wordSet.remove(t_word)
                            new_front.add(t_word)
                            ht[t_word] = pos
                    if new_front:
                        print(new_front, wordSet)
            front = new_front
        return 0

    class BSTIterator:

        def __init__(self, root: TreeNode):
            self.ls = []

            def inorder(root: TreeNode, ls):
                if not root:
                    return
                inorder(root.left, ls)
                ls.append(root.val)
                inorder(root.right, ls)

            inorder(root, self.ls)

        def next(self) -> int:
            """
            @return the next smallest number
            """
            return self.ls.pop(0)

        def hasNext(self) -> bool:
            """
            @return whether we have a next smallest number
            """
            return len(self.ls) > 0

    def findKthLargest(self, nums, k):
        import random
        l, r = 0, len(nums) - 1
        k = len(nums) - k

        def partition(arr, l, r):
            ri = random.randint(l, r)
            piv = arr[ri]
            arr[ri], arr[r] = arr[r], arr[ri]
            pos_piv = l
            for i in range(l, r):
                if arr[i] <= piv:
                    arr[i], arr[pos_piv] = arr[pos_piv], arr[i]
                    pos_piv += 1
            arr[pos_piv], arr[r] = arr[r], arr[pos_piv]
            return pos_piv

        while True:
            index = partition(nums, l, r)
            if index == k:
                return nums[index]
            if index < k:
                l = index + 1
            else:
                r = index - 1

    def findMin(self, nums):
        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left] < nums[right]:  # already sorted
                break
            mid = (left + right) // 2
            if nums[right] < nums[mid]:
                left = mid + 1  # discontinuity on RHS of mid
            elif nums[right] > nums[mid] or nums[left] > nums[mid]:
                right = mid  # discontinuity is mid or LHS
            else:  # nums[right] == nums[mid] == nums[left]
                left += 1
                right -= 1
        return nums[left]

    def findMedianSortedArrays(self, nums1, nums2):
        len1, len2 = len(nums1), len(nums2)
        if len1 > len2:
            return self.findMedianSortedArrays(nums2, nums1)

        i, j = 0, 0
        k, r = divmod(len1 + len2, 2)
        rs = []
        if not nums1:
            rs = nums2[0:k + 1]
        else:
            while i + j <= k:
                if i <= len1 - 1 and (j >= len2 or nums1[i] <= nums2[j]):
                    rs.append(nums1[i])
                    i += 1
                else:
                    rs.append(nums2[j])
                    j += 1
        if r:
            return rs[-1]
        else:
            return (rs[-1] + rs[-2]) / 2

    def test(self, arg1):
        rs = []
        lfu = Solution.LFUCache(3)
        lfu.set(2, 2)
        lfu.set(1, 1)
        rs.append(lfu.get(2))
        rs.append(lfu.get(1))
        rs.append(lfu.get(2))
        lfu.set(3, 3)
        lfu.set(4, 4)
        rs.append(lfu.get(3))
        rs.append(lfu.get(2))
        rs.append(lfu.get(1))
        rs.append(lfu.get(4))
        return rs

    import heapq
    class MinStack:

        def __init__(self):
            self.ls = []
            self.heap = []
            heapq.heapify(self.heap)

        def push(self, x: int) -> None:
            self.ls.append(x)
            heapq.heappush(self.heap, x)

        def pop(self) -> None:
            self.heap.remove(self.ls.pop())
            heapq.heapify(self.heap)

        def top(self) -> int:
            self.ls[-1]

        def getMin(self) -> int:
            if len(self.ls) == 0:
                return 0
            else:
                return self.heap[0]

    class LRUCache:

        def __init__(self, capacity: int):
            self.size = capacity
            self.dic = {}
            self.time = 0

        def get(self, key: int) -> int:
            self.time += 1
            if key in self.dic:
                p = self.dic[key]
                p[0] = self.time
                return p[1]
            else:
                return -1

        def put(self, key: int, value: int) -> None:
            if self.size <= 0:
                return
            self.time += 1
            if len(self.dic) == self.size and key not in self.dic:
                vals = list(self.dic.values())
                heapq.heapify(vals)
                evt = heapq.heappop(vals)
                del self.dic[evt[2]]
            if key not in self.dic:
                self.dic[key] = [self.time, value, key]
            else:
                p = self.dic[key]
                p[1] = value
                p[0] = self.time

    class LFUCache:
        """
        @param: capacity: An integer
        """

        def __init__(self, capacity):
            self.size = capacity
            self.dic = {}
            self.time = 0

        """
        @param: key: An integer
        @param: value: An integer
        @return: nothing
        """

        def put(self, key, value):
            if self.size <= 0:
                return
            self.time += 1
            if len(self.dic) == self.size and key not in self.dic:
                vals = list(self.dic.values())
                heapq.heapify(vals)
                evt = heapq.heappop(vals)
                del self.dic[evt[3]]
            if key not in self.dic:
                self.dic[key] = [0, self.time, value, key]
            else:
                p = self.dic[key]
                p[2] = value
                p[0] += 1
                p[1] = self.time

        """
        @param: key: An integer
        @return: An integer
        """

        def get(self, key):
            self.time += 1
            if key in self.dic:
                p = self.dic[key]
                p[0] += 1
                p[1] = self.time
                return p[2]
            else:
                return -1


if __name__ == '__main__':
    main()