class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        if n == 0 or s[0] == '0':
            return 0
        fn_2, fn_1, fn = 1, 1, 1
        for i in range(1, n):
            if s[i] == '0':
                if int(s[i-1]) > 2 or int(s[i-1]) == 0:
                    return 0
                else:
                    fn = fn_2
            else:
                fn = fn_1
                if 10 < int(s[i-1] + s[i]) < 27:
                    fn += fn_2
            fn_2, fn_1 = fn_1, fn
        return fn

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        v, w, p = 0, int(s > ''), ''
        for c in s:
            v, w, p = w, (c > '0') * w + (9 < int(p + c) < 27) * v, c
        return w
        

"""
Explanation: Lecture 1: Interview Style of FLAG
Decode Ways
https://leetcode.com/problems/decode-ways/description/
End of explanation
"""


class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        Mod = 10**9 + 7
        e0, e1, e2 = 1, 0, 0 
        for c in s:
            if c == '*':
                f0 = 9 * e0 + 9 * e1 + 6 * e2
                f1 = e0
                f2 = e0
            else:
                f0 = (c > '0') * e0 + e1 + (c < '7') * e2
                f1 = (c == '1') * e0
                f2 = (c == '2') * e0 
            e0, e1, e2 = f0 % Mod, f1, f2
        return e0
        
        

"""
Explanation: Decode Ways II
https://leetcode.com/problems/decode-ways-ii/description/
End of explanation
"""


## consider about it from the opposite way
class Solution:
    """
    @param: l1: top-left coordinate of first rectangle
    @param: r1: bottom-right coordinate of first rectangle
    @param: l2: top-left coordinate of second rectangle
    @param: r2: bottom-right coordinate of second rectangle
    @return: true if they are overlap or false
    """
    def doOverlap(self, l1, r1, l2, r2):
        # write your code here
        if l1.x > r2.x or l2.x > r1.x:
            return False
        elif l1.y < r2.y or r1.y > l2.y:
            return False
        else:
            return True

"""
Explanation: • 怎样识别动态规划类题？
– 最优化，问方法数，不需要打印所有路径的大概率是
– 看下数据范围
• 动态规划的解题步骤：
0.考虑最后一步（怎么分解，怎么走） 直觉、解题灵感来源
1.定状态
2.写转移方程
3.初始条件、边界情况
Rectangle Overlap
http://www.lintcode.com/en/problem/rectangle-overlap/
End of explanation
"""


class Solution:
    """
    @param: word: a non-empty string
    @param: abbr: an abbreviation
    @return: true if string matches with the given abbr or false
    """
    def validWordAbbreviation(self, word, abbr):
        # write your code here
        i, n = 0, '0'
        
        for c in abbr:
            if c.isdigit():
                if c == n:
                    return False
                n += c
            else:
                i += int(n)
                if i >= len(word) or word[i] != c:
                    return False
                i += 1
                n = '0'
        
        return len(word[i:]) == int(n)                

"""
Explanation: Abbreviation
Check Word Abbreviation
http://www.lintcode.com/en/problem/check-word-abbreviation/
https://leetcode.com/problems/valid-word-abbreviation/description/

Corner case: c == '0'
End of explanation
"""


import collections

class Solution:
    """
    @param: dict: an array of n distinct non-empty strings
    @return: an array of minimal possible abbreviations for every word
    """
    def wordsAbbreviation(self, dict):
        # write your code here
        self.dic = {}
        self.solve(dict, 0)
        return map(self.dic.get, dict)
        
    def abbr(self, word, size):
        if len(word) - size <= 3:
            return word
        else:
            return word[: size + 1] + str(len(word) - size - 2) + word[-1]
    
    def solve(self, dict, size):
        glist = collections.defaultdict(list)
        for word in dict:
            glist[self.abbr(word, size)].append(word)
        for abbr, words in glist.items():
            if len(words) == 1:
                self.dic[words[0]] = abbr
            else:
                self.solve(words, size+1)

dict = ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
dic = {"like": "l2e", "face": "f2e"}

list(map(dic.get, dict))

dic.get("like")

def abbr(word, size):
    if len(word) - size <= 3:
        return word
    return word[:size+1] + str(len(word) - size - 2) + word[-1]

glist = collections.defaultdict(list)
for word in dict:
    glist[abbr(word, 0)].append(word)

glist

for abbr, words in glist.items():
    print(abbr, words)

Solu = Solution()

Solu.wordsAbbreviation(dict)

list(Solu.wordsAbbreviation(dict))

list(Solu.wordsAbbreviation(dict))

"""
Explanation: Words Abbreviation
http://www.lintcode.com/en/problem/words-abbreviation/

glist[abrr] = list of words
if len(glist[abrr]) > 1 --> solve until len == 1, record dic[word] = abbr
return map(dic.get, dict): map(func, *iterables)
traverse a dict: for key, values in dic.items():
End of explanation
"""


class Solution(object):
    def generateAbbreviations(self, word):
        """
        :type word: str
        :rtype: List[str]
        """
        
        def helper(word, pos, count, cur, result):
            if pos == len(word):
                result.append(cur + (str(count) if count > 0 else ''))
            else:
                helper(word, pos + 1, count + 1, cur, result)
                helper(word, pos + 1, 0, cur + (str(count) if count > 0 else '') + word[pos], result)
        
        result = []
        helper(word, 0, 0, '', result)
        return result
        

"""
Explanation: Generalized Abbreviation
https://leetcode.com/problems/generalized-abbreviation/description/


nice problem!


a letter can be represented as a word or a number, so totally 2^n possibilities.
End of explanation
"""


class ValidWordAbbr(object):

    def __init__(self, dictionary):
        """
        :type dictionary: List[str]
        """
        self.dic = collections.defaultdict(set)
        for word in dictionary:
            self.dic[self.abbr(word)].add(word)
            
    def abbr(self, word):
        if len(word) <= 2:
            return word
        else:
            return word[0] + str(len(word) -2) + word[-1]

    def isUnique(self, word):
        """
        :type word: str
        :rtype: bool
        """
        abbr = self.abbr(word)
        if abbr not in self.dic:
            return True
        else:
            return len(self.dic[abbr]) == 1 and word in self.dic[abbr]


# Your ValidWordAbbr object will be instantiated and called as such:
# obj = ValidWordAbbr(dictionary)
# param_1 = obj.isUnique(word)

"""
Explanation: Unique Word Abbreviation
https://leetcode.com/problems/unique-word-abbreviation/description/

check the last two lines!!
End of explanation
"""


class Solution(object):
    def minAbbreviation(self, target, dictionary):
        """
        :type target: str
        :type dictionary: List[str]
        :rtype: str
        """
        
        def abbr(target, num):
            cur, count = '', 0
            for c in target:
                if num & 1 == 1:
                    if count:
                        cur += str(count)
                        count = 0
                    cur += c
                else:
                    count += 1
                num >>= 1
            if count:
                cur += str(count)
            return cur
             
            
        m, diffs = len(target), []
        for word in dictionary:
            if len(word) != m:
                continue
            
            bits = 0
            for i, c in enumerate(word):
                if target[i] != c:
                    bits += 2 ** i
            diffs += [bits]
        
        if not diffs:
            return str(m)
        
        abbrs = []
        for i in range(2 ** m):
            if all(i & d for d in diffs):
                abbrs.append(abbr(target, i))
        
        return min(abbrs, key=lambda x: len(x))
        

import operator
word = '1e4'
target = '1r2'
any(map(operator.eq, word, target))

num = 5
num >>= 1
num

num >> 1

num

diffs = []
for i in [1,2,3]:
    diffs += i,
diffs

?all

"""
Explanation: Minimum Unique Word Abbreviation
https://leetcode.com/problems/minimum-unique-word-abbreviation/description/

use bit minipulation to record the differences!
recover the abbreviation from bit record
optimization
min(abbrs, key=lambda x: len(x))
do not forget to change num in abbr function: num >>= 1
End of explanation
"""


## straight foreward
class MovingAverage:
    """
    @param: size: An integer
    """
    def __init__(self, size):
        # do intialization if necessary
        self.idx = 0
        self.sum = 0
        self.list = []
        self.size = size

    """
    @param: val: An integer
    @return:  
    """
    def next(self, val):
        # write your code here
        self.sum += val
        self.idx += 1
        if self.idx <= self.size:
            self.list += [self.sum]
            return float(self.list[-1]) / self.idx
        else:
            j = self.idx % self.size - 1
            prev = self.list[j]
            self.list[j] = self.sum
            return float(self.list[j] - prev) / self.size


# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param = obj.next(val)

"""
Explanation: Lecture 2: Simulation Algorithms & String Manipulation Skills
Sliding window
http://www.lintcode.com/zh-cn/problem/sliding-window-average-from-data-stream/
https://leetcode.com/problems/moving-average-from-data-stream/description/
End of explanation
"""


## data structure: queue
class MovingAverage(object):

    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.queue = collections.deque(maxlen=size)
        self.size = size
        self.sum = 0
        

    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        self.sum += val
        if len(self.queue) == self.size:
            self.sum -= self.queue.popleft()
        self.queue.append(val)
        return float(self.sum) / len(self.queue)

# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

import collections

collections.deque.popleft

"""
Explanation: the usage of collcections, deque, deque.popleft(), deque.append(), float()
moving sum to save memory
mode to switch index & add new vals

• 如何快速求和？ 前缀和数组(dummy 0)  
• 如何节省储存空间呢？ 链表/滚动  
• 写滚动的技巧 先写程序最后加滚动
End of explanation
"""


class Solution(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        m, n = len(s), len(t)
        if abs(m - n) > 1:
            return False
        elif m < n:
            return self.isOneEditDistance(t, s)
        else:
            for i in range(n):
                if s[i] != t[i]:
                    if m == n:
                        return s[i+1:] == t[i+1:]
                    else:
                        return s[i+1:] == t[i:]
        
        return m != n
        

s = '12dere'
n = len(s)
s[n:]

"""
Explanation: One Edit Distance
https://leetcode.com/problems/one-edit-distance/description/
End of explanation
"""


# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):

class Solution(object):
    def read(self, buf, n):
        """
        :type buf: Destination buffer (List[str])
        :type n: Maximum number of characters to read (int)
        :rtype: The number of characters read (int)
        """
        idx = 0
        while True:
            buf4 = [""]*4
            curr = min(read4(buf4), n-idx)
            for i in range(curr):
                buf[idx] = buf4[i]
                idx += 1
            if curr != 4 or idx == n:
                return idx

buf4 = [""]*4
buf4

"""
Explanation: Read N Characters Given Read4  (not clear)
https://leetcode.com/problems/read-n-characters-given-read4/description/
End of explanation
"""


# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):

class Solution(object):
    def __init__(self):
        self.queue = []
    
    
    def read(self, buf, n):
        """
        :type buf: Destination buffer (List[str])
        :type n: Maximum number of characters to read (int)
        :rtype: The number of characters read (int)
        """
        idx = 0
        while True:
            buf4 = [""]*4
            l = read4(buf4)
            self.queue.extend(buf4)
            curr = min(len(self.queue), n-idx)
            for i in range(curr):
                buf[idx] = self.queue.pop(0)
                idx += 1
            if curr == 0:
                break
        
        return idx

buf4 = [""]*4
queue1, queue2 = [], []
queue1.append(buf4)
queue2.extend(buf4)
queue1, queue2

"""
Explanation: Read Characters From File - multiple calls
https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/description/

init function: def inti(self):
differece between append and extend

难点： 
• 如果只读3个，剩下的一个怎么处理？（读多的怎么留着给下次用？） 
• Read4 这个函数只读了2个怎么办？ （读到末尾时，没有读全4个）
End of explanation
"""


class Solution:
    """
    @param: strs: a list of strings
    @return: encodes a list of strings to a single string.
    """
    def encode(self, strs):
        # write your code here
        res = ''
        for s in strs:
            for c in s:
                if c == ":":
                    res += "::"
                else:
                    res += c
            res += ":;"
        return res

    """
    @param: str: A string
    @return: dcodes a single string to a list of strings
    """
    def decode(self, str):
        # write your code here
        res = []
        s = ''
        i = 0
        while i < len(str) - 1:
            if str[i] == ":":
                if str[i+1] == ";":
                    res += [s]
                    s = ''
                else:
                    s += str[i+1]
                i += 2
            else:
                s += str[i]
                i += 1
        return res

"""
Explanation: Strings Serialization
http://www.lintcode.com/zh-cn/problem/strings-serialization/
• abc def -> abc:;def:;
• ab:c def -> ab::c:;def:;
• ab:;c def -> ab::;c:;def:;
• 用‘：’表示转义，那么连接符就是’：；’ 表示‘：’本身就是‘：：’
End of explanation
"""


len("dir/subdir2/subsubdir2/file2.ext")

s = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"

s.splitlines()

line = '\t\tfile.ext'
line.lstrip('\t')

class Solution(object):
    def lengthLongestPath(self, input):
        """
        :type input: str
        :rtype: int
        """
        maxlen = 0
        pathlen = {0:0}
        for line in input.splitlines():
            name = line.lstrip('\t')
            depth = len(line) - len(name)
            if '.' in name:
                maxlen = max(maxlen, pathlen[depth] + len(name))
            else:
                pathlen[depth+1] = pathlen[depth] + len(name) + 1
        
        return maxlen

"""
Explanation: System Longest File Path
https://leetcode.com/problems/longest-absolute-file-path/description/

splitlines() and lstrip('\t')
End of explanation
"""


class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        if len(s) == 0:
            return 0
        res = roman[s[-1]]
        idx = len(s) - 2
        while idx >= 0:
            if roman[s[idx]] < roman[s[idx+1]]:
                res -= roman[s[idx]] 
            else:
                res += roman[s[idx]] 
            idx -= 1
        
        return res

"""
Explanation: Roman to Integer
https://leetcode.com/problems/roman-to-integer/description/
End of explanation
"""


class Solution(object):
    def parse(self, digit, index):
        nums = {1: "I", 2: "II", 3: "III", 4: "IV", 5: "V", 6: "VI", 7: "VII", 8: "VIII", 9: "IX"}
        roman = {
            "I": ["I", "X", "C", "M"],
            "V": ["V", "L", "D", "?"],
            "X": ["X", "C", "M", "?"]
        }
        s = nums[digit]
        return s.replace("X", roman["X"][index]).replace("V", roman["V"][index]).replace("I", roman["I"][index])
  
    
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        
        ans = ""
        index = 0
        while num > 0:
            digit = num % 10
            if digit != 0:
                ans = self.parse(digit, index) + ans
            num = int(num / 10)
            index += 1
        
        return ans

    
#         # solution 1
#         nums = [
#             ["I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"],
#             ["X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"],
#             ["C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"],
#             ["M", "MM", "MMM"]
#         ]
        
#         ans = ""
#         row = 0
#         while num > 0:
#             digit = num % 10
#             if digit != 0:
#                 ans = nums[row][digit-1] + ans
#             num = num / 10
#             row += 1
#         return ans

"""
Explanation: Integer to Roman
https://leetcode.com/problems/roman-to-integer/description/
End of explanation
"""


# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):

class Solution(object):
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        candidate = 0
        for i in range(1, n):
            if knows(candidate, i):
                candidate = i
        
        for i in range(candidate):
            if not knows(i, candidate) or knows(candidate, i):
                return -1
        
        for i in range(candidate+1, n):
            if not knows(i, candidate) or knows(candidate, i):
                return -1
        
        return candidate
                
        

"""
Explanation: Find the Celebrity
https://leetcode.com/problems/find-the-celebrity/description/
End of explanation
"""


nums = [0, 1, 3, 50, 75]

for k, v in enumerate(nums):
    print(k, v, nums[k])

class Solution(object):
    def findMissingRanges(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: List[str]
        """
        res = []
        start = lower
        for k, v in enumerate(nums):  # 两端点和一头一尾形成的区间 + for循环扫描中间形成的区间
            if v < start:
                continue
            elif v == start:
                start += 1
                continue
            res.append(self.addRange(start, v-1))
            start = v + 1
        if start <= upper:   # corner case
            res.append(self.addRange(start, upper))
        return res
                              
    def addRange(self, start, end):  # – 利用函数让自己的代码更简洁 （见代码）
        return str(start) if start == end else str(start) + "->" + str(end)

"""
Explanation: Lecture 3: Basic Algorithms & Data Structure I
Missing Ranges
https://leetcode.com/problems/missing-ranges/description/
End of explanation
"""


starts = [2, 1, 15, 8]
idx = sorted(range(len(starts)), key=lambda x: starts[x])
idx

intervals = [[8,10], [2,6]]
intervals.sort()

intervals

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        intervals = sorted(intervals, key=lambda x: x.start)  # sort skill !!!
        res = []
        for interval in intervals:
            if len(res) == 0 or res[-1].end < interval.start:  # when to add interval
                res.append(interval)
            else:
                res[-1].end = max(res[-1].end, interval.end)
        return res

"""
Explanation: Merge Intervals
https://leetcode.com/problems/merge-intervals/description/
End of explanation
"""


# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        intervals = intervals + [newInterval]
        intervals = sorted(intervals, key=lambda x: x.start)
        res = []
        for interval in intervals:
            if len(res) == 0 or res[-1].end < interval.start:
                res.append(interval)
            else:
                res[-1].end = max(res[-1].end, interval.end)
        return res
        

"""
Explanation: Insert Interval
https://leetcode.com/problems/insert-interval/description/
End of explanation
"""


dic = {'1':[1,5,8], '0':[2,4,3]}

for key, value in dic.items():
    print(key, value)

class Solution:
    """
    @param: s: a string
    @return: it's index
    """
    def firstUniqChar(self, s):
        # write your code here
        dic = {}
        for c in s:
            dic[c] = dic.get(c, 0) + 1
        for i in range(len(s)):
            if dic[s[i]] == 1:
                return i
        return -1

"""
Explanation: First Position Unique Character
http://www.lintcode.com/zh-cn/problem/first-position-unique-character/
End of explanation
"""


ord('a'), chr(97)

abs([1,2])

from collections import Counter
Counter('aba')

dic = {'a': 2, 'b': 1}

del dic['a']
dic

# class Solution(object):
#     def findAnagrams(self, s, p):
#         """
#         :type s: str
#         :type p: str
#         :rtype: List[int]
#         """
#         m, n = len(s), len(p)
#         res = []
#         if m < n:
#             return res
#         pc = collections.Counter(p)
#         sc = collections.Counter(s[:n-1])
#         for i in range(m-n+1):
#             sc[s[n-1+i]] += 1
#             if sc == pc:
#                 res.append(i)
#             sc[s[i]] -= 1
#             if sc[s[i]] == 0:
#                 del sc[s[i]]
#         return res

class Solution:
    """
    @param: s: a string
    @param: p: a string
    @return: a list of index
    """
    def findAnagrams(self, s, p):
        # write your code here
        m, n = len(s), len(p)
        res = []
        if m < n:
            return res
        det = [0 for i in range(26)]
        for i in range(n):
            jp = ord(p[i]) - ord('a')
            det[jp] -= 1
            js = ord(s[i]) - ord('a')
            det[js] += 1
        
        
        sum = 0
        for d in det:
            sum += abs(d)
        if sum == 0:
            res.append(0)
        for i in range(0, m-n):
            jl = ord(s[i]) - ord('a')
            sum -= abs(det[jl])
            det[jl] -= 1
            sum += abs(det[jl])
            jr = ord(s[i+n]) - ord('a')
            sum -= abs(det[jr])
            det[jr] += 1
            sum += abs(det[jr])
            if sum == 0:
                res.append(i+1)
        
        return res

"""
Explanation: Substring Anagrams
http://www.lintcode.com/zh-cn/problem/substring-anagrams/
https://leetcode.com/problems/find-all-anagrams-in-a-string/description/
End of explanation
"""


set().union('he'), set().union(['he'])

len(set().union('he'))

def getAbbr(word):
    if len(word) > 2:
        return word[0] + str(len(word) - 2) + word[-1]
    return word

d = collections.defaultdict(set)
for word in ['aa', 'bb', 'cc', 'cc','bb']:
    d[getAbbr(word)].add(word)
d

collections.defaultdict?

class ValidWordAbbr(object):

    def __init__(self, dictionary):
        """
        :type dictionary: List[str]
        """
        self.dic = collections.defaultdict(set)
        for word in dictionary:
            self.dic[self.getAbbr(word)].add(word)
        
    
    def getAbbr(self, word):
        return word if len(word) < 3 else word[0] + str(len(word)-2) + word[-1]
        

    def isUnique(self, word):
        """
        :type word: str
        :rtype: bool
        """
        abbr = self.getAbbr(word)
        if abbr not in self.dic:
            return True
        else:
            return len(self.dic[abbr]) == 1 and word in self.dic[abbr]
        


# class ValidWordAbbr(object):

#     def __init__(self, dictionary):
#         """
#         :type dictionary: List[str]
#         """
#         self.dic = {}
#         for word in dictionary:
#             abrr = self.abrr(word)
#             self.dic[abrr] = self.dic.get(abrr, set()).union([word])
            
            
#     def abrr(self, word):
#         return word if len(word) < 3 else word[0] + str(len(word)-2) + word[-1]
    

#     def isUnique(self, word):
#         """
#         :type word: str
#         :rtype: bool
#         """
#         abrr = self.abrr(word)
#         if abrr in self.dic:
#             if len(self.dic[abrr]) > 1 or word not in self.dic[abrr]:
#                 return False
#         return True  
        
        


# # Your ValidWordAbbr object will be instantiated and called as such:
# # obj = ValidWordAbbr(dictionary)
# # param_1 = obj.isUnique(word)

"""
Explanation: Word Abbreviation Set
http://www.lintcode.com/zh-cn/problem/word-abbreviation-set/
https://leetcode.com/problems/unique-word-abbreviation/description/
End of explanation
"""


class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = {}
        for n in nums:
            dic[n] = False
        
        maxlen = 0
        for n in nums:
            if dic[n]:
                continue
            length = 1
            left, right = n - 1, n + 1
            while left in dic:
                length += 1
                dic[left] = True
                left -= 1
            while right in dic:
                length += 1
                dic[right] = True
                right += 1
            maxlen = max(maxlen, length)
        return maxlen

"""
Explanation: Longest Consecutive Sequence
https://leetcode.com/problems/longest-consecutive-sequence/description/
End of explanation
"""


a = set().union('he')

a = [0, 1, 2]
a.pop()
a

import random
for i in range(15):
    print(random.randint(0, 5 - 1))

class LoadBalancer:
    def __init__(self):
        # do intialization if necessary
        self.ids = []
        self.index = {}

    """
    @param: server_id: add a new server to the cluster
    @return: nothing
    """
    def add(self, server_id):
        # write your code here
        self.ids.append(server_id)
        self.index[server_id] = len(self.ids) - 1

    """
    @param: server_id: server_id remove a bad server from the cluster
    @return: nothing
    """
    def remove(self, server_id):
        # write your code here
        idx = self.index[server_id]
        del self.index[server_id]
        last_id = self.ids[-1]
        self.index[last_id] = idx
        self.ids[idx] = last_id
        self.ids.pop()

    """
    @return: pick a server in the cluster randomly with equal probability
    """
    def pick(self):
        # write your code here
        import random
        idx = random.randint(0, len(self.ids)-1)
        return self.ids[idx]

"""
Explanation: Load Balancer
http://www.lintcode.com/en/problem/load-balancer/
End of explanation
"""


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.sum = 0
        self.dfs(root)
        return root
        
    def dfs(self, root):
        if root is None:
            return 
        if root.right:
            self.dfs(root.right)
        self.sum += root.val
        root.val = self.sum
        if root.left:
            self.dfs(root.left)

"""
Explanation: Lecture 4: Basic Algorithms & Data Structure II
Binary Search
Convert BST to Greater Tree
https://leetcode.com/problems/convert-bst-to-greater-tree/description/
End of explanation
"""


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        succ = None
        while root:
            if root.val <= p.val:
                root = root.right
            else:
                succ = root
                root = root.left
        return succ
        

"""
Explanation: Inorder Successor in BST
https://leetcode.com/problems/inorder-successor-in-bst/description/

Depth First Traversals: 

(a) Inorder (Left, Root, Right) : 4 2 5 1 3
(b) Preorder (Root, Left, Right) : 1 2 4 5 3
(c) Postorder (Left, Right, Root) : 4 5 2 3 1
End of explanation
"""


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def upsideDownBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root is None or root.left is None:
            return root
        
        new_root = self.upsideDownBinaryTree(root.left)
        root.left.left = root.right
        root.left.right = root
        root.left = None
        root.right = None
        return new_root

"""
Explanation: Binary Tree Upside Down
https://leetcode.com/problems/binary-tree-upside-down/description/
End of explanation
"""


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        result = []
        self.dfs(root, result)
        return result
    
    def dfs(self, root, result):
        if root is None:
            return 0
        
        level = max(self.dfs(root.left, result), self.dfs(root.right, result)) + 1
        if level > len(result):
            result.append([])
        result[level-1].append(root.val)
        return level
        

"""
Explanation: Find Leaves of Binary Tree
https://leetcode.com/problems/find-leaves-of-binary-tree/description/
End of explanation
"""


a = []
a.append((1,2))
a

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        result = collections.defaultdict(list)
        level = [(root, 0)]
        while level:
            next_level = []
            for node, order in level:
                if node:
                    result[order].append(node.val)
                    next_level.append((node.left, order-1))
                    next_level.append((node.right, order+1))
            level = next_level
        return [result[i] for i in sorted(result)]
    

"""
Explanation: Binary Tree Vertical Order Traversal
https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/
End of explanation
"""


## version 1: traversal
queue = [start]
while queue:
    node = queue.pop(0)
    new_node = node + 1 # or other conditions
    queue.append(new_node)
    
    
## version 2: length of shortest path
length, level = 0, [start]
while level:
    new_level = []
    for node in level:
        new_node = node + 1
        new_level.append(new_node)
    length += 1
    level = new_level

"""
Explanation: Lecture 5: How to Implement Search Problem Effectively
1.BFS是用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解，因为BFS搜索过程中遇到的解一定是离根最近的，所以遇到一个解，一定就是最优解，此时搜索算法可以终止。这个时候不适宜使用DFS，因为DFS搜索到的解不一定是离根最近的，只有全局搜索完毕，才能从所有解中找出离根的最近的解。（当然这个DFS的不足，可以使用迭代加深搜索ID-DFS去弥补）
2.空间优劣上，DFS是有优势的，DFS不需要保存搜索过程中的状态，而BFS在搜索过程中需要保存搜索过的状态，而且一般情况需要一个队列来记录。
3.DFS适合搜索全部的解，因为要搜索全部的解，那么BFS搜索过程中，遇到离根最近的解，并没有什么用，也必须遍历完整棵搜索树，DFS搜索也会搜索全部，但是相比DFS不用记录过多信息，所以搜素全部解的问题，DFS显然更加合适。
4.基本原则：能用BFS的时候就用BFS，不能用的时候再用DFS。
BFS
Template
End of explanation
"""


any?

any([[]])

row = 'XXSi'
['XO'[c == 'S'] for c in row]

board = ["XXXX","XOOX","XXOX","XSXX"]
board[:] = [['XO'[c == 'S'] for c in row] for row in board]
board

board = [list("XXXX"),list("XOOX"),list("XXOX"),list("XSXX")]
for row in board:
    for i, c in enumerate(row):
        row[i] = 'XO'[c == 'S']
board

class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if not any(board):
            return 
        
        m, n = len(board), len(board[0])
        save = [ij for k in range(max(m,n)) for ij in ((0, k), (m-1, k), (k, 0), (k, n-1))]
        while save:
            i, j = save.pop()
            if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
                board[i][j] = 'S'
                save += (i+1, j), (i-1, j), (i, j+1), (i, j-1)
        
        for row in board:
            for i, c in enumerate(row):
                if c == 'S':
                    row[i] = 'O'
                else:
                    row[i] = 'X'
        
#         for row in board:
#             for i, c in enumerate(row):
#                 row[i] = 'XO'[c == 'S']
        
#         board[:] = [['XO'[c == 'S'] for c in row] for row in board]


c = Solution()
board = [list("XXXX"),list("XOOX"),list("XXOX"),list("XOXX")] # board is a list of list !!!
c.solve(board)
board

"""
Explanation: Surrounded Regions
https://leetcode.com/problems/surrounded-regions/description/
小技巧总结：
• 在网格图、矩阵图、棋盘上做多个方向扩展时，用dx dy数组会让程序写起
来更方便
End of explanation
"""


class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        if not any(rooms): return 
        IFN = 2147483647
        m, n = len(rooms), len(rooms[0])
        queue = [(i, j) for i, row in enumerate(rooms) for j, c in enumerate(row) if c == 0]
        while queue:
            i, j = queue.pop(0)
            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                if 0 <= x < m and 0 <= y < n and rooms[x][y] == IFN:
                    rooms[x][y] = rooms[i][j] + 1
                    queue.append((x, y))

"""
Explanation: Nearest Exit
https://leetcode.com/problems/walls-and-gates/description/
 小技巧总结：
– 多源点单终点 --> 单源点多终点，最短路常用转化套路
– 多源多终点 --> 单源多终点 （增加超级源，最短路常用转化套路）
– BFS可以求边长=1的图的最短路（如此题的棋盘图）
End of explanation
"""


## version 1: traversal
stack = [start]
while stack:
    node = stack.pop()
    new_node = node + 1 # or other conditions
    stack.append(new_node)
    
    
## version 2: Divide & Conquer
def dfs(root): # ex: binary tree
    ## null or leaf
    if root is None:
        ## do something and return;

    ## Divide
    left = dfs(root.left);
    right = dfs(root.right);

    ## Conquer
    result = Merge(left, right)
    return result

"""
Explanation: DFS
Template
End of explanation
"""


digits ='23'
chr = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
res = []


for i in range(len(digits)):
    num = int(digits[i])
    temp = []
    for c in chr[num]:
        if len(res) == 0:
            temp += [c]
        else:
            for r in res:
                temp += [r + c]
    res[:] = temp
res
        

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        n, res = len(digits), []
        if n == 0: return res
        letters = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        for i in range(n):
            num = int(digits[i])
            temp = []
            for c in letters[num]:
                if len(res) == 0:
                    temp.append(c)
                else:
                    for j in range(len(res)):
                        temp.append(res[j]+c)
            res[:] = temp
        return res
        

# 思路：
# • 基础枚举型DFS（按方法1 执行过程理解）
# – 输入数字串长度为n，做n个阶段的选择，DFS n层
# – 每一阶段枚举该位的数字对应的一个字母
# – 直到所有情况都枚举完

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        def dfs(num, string, res):
            if num == n:
                res.append(string)
                return 
            for c in letters[int(digits[num])]:
                dfs(num+1, string+c, res)
        
        n, res = len(digits), []
        if n == 0: return res
        letters = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        dfs(0, '', res)
        return res
        

"""
Explanation: Letter Combinations of a Phone Number
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
End of explanation
"""


a = []
a.append([1,2,3])
a.append([2,3])
a

class Solution:
    """
    @param: n: An integer
    @return: a list of combination
    """
    def getFactors(self, n):
        # write your code here
        
        def dfs(start, remain):
            if remain == 1:
                if len(path) > 1:
                    print(path, result)
                    result.append(path)
                    print(result)
                return 
            
            for i in range(start, remain):
                if i > int(remain / i):
                    break
                if remain % i == 0:
                    path.append(i)
                    dfs(i, int(remain/i))
                    path.pop()
            
            path.append(remain)
            dfs(remain, 1)
            path.pop()
#             print(result)
        
        result, path = [], []
        dfs(2, n)
        return result

c = Solution()

c.getFactors(8)

a = [[2, 2, 2]]
a.append([2,4])
a += [[1]]
a

# 思路：
# • DFS：
# – 扩展：枚举每一个位置的因子
# • 每次从前一个枚举的因子start开始枚举，以保证枚举因子的顺序是从小到大
# – 退出条件：n除以已枚举因子之后还剩的数remain = 1 时

# • 用什么方法记录状态
# – start、remain采用方法1 放到DFS函数的参数中
# – 记录已枚举因子的数组path采用方法3 成员变量手动模拟栈


class Solution:
    """
    @param: n: An integer
    @return: a list of combination
    """
    def getFactors(self, n):
        # write your code here
        def dfs(start, remain):
            if remain == 1:
                if len(path) > 1:
                    result.append(path[:])
                return
            
            for i in range(start, int(remain**0.5) + 1):
                if remain % i == 0:
                    path.append(i)
                    dfs(i, remain/i)
                    path.pop()
            
            path.append(remain)
            dfs(start, 1)
            path.pop()
        
        path, result = [], []
        dfs(2, n)
        return result

"""
Explanation: Factorization
http://www.lintcode.com/zh-cn/problem/factorization/

Note: 

(1) the way to add path
(2) the way to copy temp in the last problem
End of explanation
"""


alist = ['a1', 'a2', 'a3']
blist = ['b1', 'b2', 'b3']

for i, (a, b) in enumerate(zip(alist, blist)):
    print(i, a, b)

class Solution(object):
    def wordSquares(self, words):
        """
        :type words: List[str]
        :rtype: List[List[str]]
        """
        n, res = len(words[0]), []
        starts = collections.defaultdict(list)
        for i in range(1, n):
            for word in words:
                starts[word[:i]].append(word)
        
        def dfs(square):
            k = len(square)
            if k == n:
                res.append(square)
                return
            start = ''
            for i in range(k):
                start += square[i][k]
            for word in starts[start]:
                dfs(square + [word])
        
        for word in words:
            dfs([word])
        
        return res

"""
Explanation: Word Squares
https://leetcode.com/problems/word-squares/description/
End of explanation
"""


class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        n, res = len(num), []
        def dfs(left, temp, cur, last):
            if len(left) == 0:
                if cur == target:
                    res.append(temp[:])
                return
            
            for i in range(1, len(left)+1):
                val = left[:i]
                if i == 1 or (i > 1 and left[0] != '0'):
                    dfs(left[i:], temp + '+' + val, cur + int(val), int(val))
                    dfs(left[i:], temp + '-' + val, cur - int(val), -int(val))
                    dfs(left[i:], temp + '*' + val, cur -last + last*int(val), last*int(val))
        
        for i in range(1, n+1):
            if i == 1 or (i > 1 and num[0] != '0'):
                dfs(num[i:], num[:i], int(num[:i]), int(num[:i]))
        
        return res
                    

"""
Explanation: Expression Add Operators
https://leetcode.com/problems/expression-add-operators/description/
End of explanation
"""


# binary search template
while start + 1 < end:
    mid = start + (end - start) / 2
    if ....

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        m, n = len(matrix), len(matrix[0])
        start, end = 0, m*n - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            i = mid / n
            j = mid % n
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                end = mid - 1
            else:
                start = mid + 1
        
        i = start / n
        j = start % n
        if matrix[i][j] == target:
            return True
        
        i = end / n
        j = end % n
        if matrix[i][j] == target:
            return True
        
        return False

"""
Explanation: Lecture 6: Math, Computational Graphic, Bit Operation
Search a 2D Matrix  (Binary search!!!)
https://leetcode.com/problems/search-a-2d-matrix/description/
End of explanation
"""


class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        
        m, n = len(matrix), len(matrix[0])
        r, c = 0, n-1
        while r < m and c >= 0:
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] > target:
                c -= 1
            else:
                r += 1
        
        return False

"""
Explanation: Search a 2D Matrix II
https://leetcode.com/problems/search-a-2d-matrix-ii/description/
End of explanation
"""


for i in range(-1):
    print(i)

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        for i in range(m):
            for j in range(n/2):
                matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]


"""
Explanation: Rotate Image
https://leetcode.com/problems/rotate-image/description/
End of explanation
"""


class Solution(object):
    def multiply(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: List[List[int]]
        """
        
        m, n, l = len(A), len(B), len(B[0])
        dicA, dicB = {}, {}
        for i in range(m):
            for j in range(n):
                if A[i][j] != 0:
                    dicA[i] = dicA.get(i, []) + [(j, A[i][j])]
                
        for i in range(n):
            for j in range(l):
                if B[i][j] != 0:
                    dicB[i] = dicB.get(i, []) + [(j, B[i][j])]
        
        C = [[0 for j in range(l)] for i in range(m)]
        
        for i in dicA:
            for a in dicA[i]:
                j = a[0]
                if j in dicB:
                    for b in dicB[j]:
                        k = b[0]
                        C[i][k] += a[1]*b[1]
        return C
        
        
#         # faster       
#         m, n, l = len(A), len(B), len(B[0])
#         C = [[0 for j in range(l)] for i in range(m)]
        
#         for i in range(m):
#             for j in range(n):
#                 if A[i][j] != 0:
#                     for k in range(l):
#                         C[i][k] += A[i][j]*B[j][k]
#         return C
        

"""
Explanation: Sparse Matrix Multiplication
https://leetcode.com/problems/sparse-matrix-multiplication/description/
End of explanation
"""


class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        i, j = len(num1) - 1, len(num2) - 1
        carry, res = 0, ''
        while i >= 0 or j >= 0:
            if i >= 0:
                carry += ord(num1[i]) - ord('0')
                i -= 1
            if j >= 0:
                carry += ord(num2[j]) - ord('0')
                j -= 1
            res = str(carry % 10) + res
            carry /= 10
        
        return res if carry == 0 else str(carry) + res
        

"""
Explanation: Bit operation
Big Integer Addition
http://www.lintcode.com/zh-cn/problem/big-integer-addition/
https://leetcode.com/problems/add-strings/description/


ord(num1[i]) - ord('0') is faster than int(num1[i])


do not forget i -= 1
End of explanation
"""


class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        i, j = len(a) - 1, len(b) - 1
        res, carry = '', 0
        while i >= 0 or j >= 0:
            if i >= 0:
                if a[i] == '1':
                    carry += 1
                i -= 1
            if j >= 0:
                if b[j] == '1':
                    carry += 1
                j -= 1
            res = str(carry % 2) + res
            carry /= 2
        return res if carry == 0 else '1' + res
        

"""
Explanation: Add Binary
https://leetcode.com/problems/add-binary/description/
End of explanation
"""


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        p = dummy
        carry = 0
        while True:
            if l1 is not None:
                carry += l1.val
                l1 = l1.next
            if l2 is not None:
                carry += l2.val
                l2 = l2.next
            p.val = carry % 10
            carry /= 10
            if l1 is not None or l2 is not None or carry != 0:
                temp = ListNode(0)
                p.next = temp
                p = p.next
            else:
                break
        
        return dummy

"""
Explanation: Add Two Numbers
http://www.lintcode.com/en/problem/add-two-numbers/
https://leetcode.com/problems/add-two-numbers/description/
End of explanation
"""


a = [1,2,3]

a.pop()

a

a.pop(0)

a.pop()

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        nums1, nums2 = [], []
        while l1 is not None:
            nums1.append(l1.val)
            l1 = l1.next
        while l2 is not None:
            nums2.append(l2.val)
            l2 = l2.next
        
        res = ListNode(0)
        carry = 0
        while len(nums1) > 0 or len(nums2) > 0:
            if len(nums1) > 0:
                carry += nums1.pop()
            if len(nums2) > 0:
                carry += nums2.pop()
            res.val = carry % 10
            carry /= 10
            p = ListNode(carry)
            p.next = res
            res = p
        return res if res.val != 0 else res.next
        

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l1 = self.reverseList(l1)
        l2 = self.reverseList(l2)
        dummy = ListNode(0)
        p = dummy
        carry = 0
        while True:
            if l1 is not None:
                carry += l1.val
                l1 = l1.next
            if l2 is not None:
                carry += l2.val
                l2 = l2.next
            p.val = carry % 10
            carry /= 10
            if l1 is not None or l2 is not None or carry != 0:
                p.next = ListNode(0)
                p = p.next
            else:
                break
        return self.reverseList(dummy)
        
        
        
    def reverseList(self, l):
        prev = None
        while l:
            curr = l
            l = l.next
            curr.next = prev
            prev = curr
        return prev
        

"""
Explanation: Add Two Numbers¶ II
https://leetcode.com/problems/add-two-numbers-ii/description/


stack


reverse a linked list !!!
End of explanation
"""


'0'*0

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        len1, len2 = len(num1), len(num2)
        num3 = [0] * (len1 + len2)
        for i in range(len1-1, -1, -1):
            carry = 0
            for j in range(len2-1, -1, -1):
                product = num3[i + j + 1] + carry + (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                num3[i + j + 1] = product % 10
                carry = product / 10
            num3[i] = carry
        
        res = ''
        i = 0
        while i < len1 + len2 - 1 and num3[i] == 0:
            i += 1
        while i < len1 + len2:
            res += str(num3[i])
            i += 1
        return res
            
                
        

"""
Explanation: Big Integer multiplication
http://www.lintcode.com/en/problem/big-integer-multiplication/
https://leetcode.com/problems/multiply-strings/description/
End of explanation
"""


n = -3
-n

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1
        if n < 0:
            x = 1.0 / x
            n = -n
        
        res = 1
        temp = x
        while n != 0:
            if n % 2 == 1:
                res *= temp
            temp *= temp
            n /= 2
        
        return res
        

"""
Explanation: Pow(x, n)
https://leetcode.com/problems/powx-n/description/
End of explanation
"""


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev = None
        while head is not None:
            curr = head
            head = head.next  # do not mass up the order !!!
            curr.next = prev
            prev = curr
        return prev
        

"""
Explanation: Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/description/

do not mass up the order !!!
End of explanation
"""


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        mth_prev = self.find_kth(dummy, m-1)
        mth = mth_prev.next
        nth = self.find_kth(dummy, n)
        nth_next = nth.next
        nth.next = None
        self.reverse(mth)
        
        mth_prev.next = nth
        mth.next = nth_next
        return dummy.next

        
    def reverse(self, head):
        prev = None
        while head is not None:
            curr = head
            head = head.next
            curr.next = prev
            prev = curr
        return prev
    
    def find_kth(self, head, k):
        for i in range(k):
            if head is None:
                return None
            head = head.next
        return head
        

"""
Explanation: Reverse Linked List II
https://leetcode.com/problems/reverse-linked-list-ii/description/
End of explanation
"""


