Page tree

Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Code Block
languagepy
titleanswerMinimum Swaps 2
def swap(arr, a, b):
    arr[a], arr[b] = arr[b], arr[a]
    return arr

def minimumSwaps(arr):
    idx = 0
    arr_len = len(arr)
    swap_cnt = 0
    while idx < arr_len:
        if arr[idx] == arr[arr[idx] - 1]:
            idx += 1
            continue
        swap(arr, idx, arr[idx] - 1)
        idx += 1
        swap_cnt += 1
        idx -= 1
    return swap_cnt


2. 

Code Block
languagepy
titleanswerSherlock and Anagrams
def cal_comb(n, r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))


def sorted_str(s):
    return ''.join(sorted(s))


def sherlockAndAnagrams(s):
    dic = {}
    str_len = len(s)
    for ngram_size in range(1, str_len):
        for start in range(0, str_len + 1 - ngram_size):
            ngram = s[start:start + ngram_size]
            ngram = sorted_str(ngram)
            if ngram not in dic:
                dic[ngram] = 1
            else:
                dic[ngram] += 1

    total = 0
    for key in dic:
        n = dic[key]
        if n >= 2:
            total += cal_comb(n, 2)

    return total

...