-
Notifications
You must be signed in to change notification settings - Fork 0
/
Sherlock and Anagrams.py
83 lines (68 loc) · 2.71 KB
/
Sherlock and Anagrams.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
# -*- coding: utf-8 -*-
"""
Created on Thu Apr 23 18:16:00 2020
@author: TheKa
"""
#!/bin/python3
import math
import os
import random
import re
import sys
# Complete the sherlockAndAnagrams function below.
def sherlockAndAnagrams(s):
mat = {}
len_s = len(s)
anagrams = 0
for i in range(len_s):
for j in range(len_s):
mat[(i,j)] = set()
for first in range(len_s):
for second in range(len_s):
if s[first]==s[second] and first!=second:
mat[(first,first)].add((second,second))
beg = min(first,second)
end = max(first,second)
mat[(beg+1,end)].add((beg,end-1))
mat[(beg,end-1)].add((beg+1,end))
anagrams += len(mat[(first,first)])
for size in range(1,len_s):
for beg in range(len_s-size):
end = beg+size
m1 = s[beg]
m2 = s[end]
if beg+1<=end:
for beg_x,end_x in mat[(beg+1,end)]:
if beg_x>0 and beg_x-1!=beg and m1 == s[beg_x-1]:
mat[(beg,end)].add((beg_x-1,end_x))
if beg_x-2>beg and end+1>end_x:
mat[(beg,beg_x-2)].add((end+1,end_x))
mat[(end+1,end_x)].add((beg,beg_x-2))
if end_x<len_s-1 and end_x+1!=end and m1 == s[end_x+1]:
mat[(beg,end)].add((beg_x,end_x+1))
if beg_x-2>beg and end+1>end_x:
mat[(beg,beg_x-2)].add((end+1,end_x))
mat[(end+1,end_x)].add((beg,beg_x-2))
if beg<=end-1:
for beg_x,end_x in mat[(beg,end-1)]:
if beg_x>0 and beg_x-1!=beg and m2 == s[beg_x-1]:
mat[(beg,end)].add((beg_x-1,end_x))
if beg_x-2>beg and end+1>end_x:
mat[(beg,beg_x-2)].add((end+1,end_x))
mat[(end+1,end_x)].add((beg,beg_x-2))
if end_x<len_s-1 and end_x+1!=end and m2 == s[end_x+1]:
mat[(beg,end)].add((beg_x,end_x+1))
if beg_x-2>beg and end+1>end_x:
mat[(beg,beg_x-2)].add((end+1,end_x))
mat[(end+1,end_x)].add((beg,beg_x-2))
anagrams += len(mat[(beg,end)])
for i in mat.keys():
if len(mat[i])>0:
print(i,mat[i])
print(mat)
return anagrams//2
q = int(input())
for q_itr in range(q):
s = input()
result = sherlockAndAnagrams(s)
print(str(result) + '\n')