Group Shifted Strings - LeetCode
We can shift a string by shifting each of its letters to its successive letter.
For example, “abc” can be shifted to be “bcd”.We can keep shifting the string to form a sequence.
For example, we can keep shifting “abc” to form the sequence: “abc” -> “bcd” -> … -> “xyz”.Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.
Example 1: Input: strings = [“abc”,“bcd”,“acef”,“xyz”,“az”,“ba”,“a”,“z”] Output: [[“acef”],[“a”,“z”],[“abc”,“bcd”,“xyz”],[“az”,“ba”]]
Example 2: Input: strings = [“a”] Output: [[“a”]]
Constraints:
1 <= strings.length <= 200
1 <= strings[i].length <= 50
strings[i] consists of lowercase English letters.
- code
class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strings:
# key = "".join(chr((ord(c)-ord(s[0]))%26) for c in s)
key = tuple((ord(c) - ord(s[0])) % 26 for c in s)
d[key].append(s)
return list(d.values())
Python, -2 % 5 = 3, it’s like (-2 + 5) % 5
- code wrong, thought it means consecutive numbers
class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]]:
group = defaultdict(list)
res = []
def getDirection(x, y):
diff = ord(x) - ord(y)
if diff == 1 or diff == -25: return 1
elif diff == -1 or diff == 25: return -1
else: return 0
for s in strings:
if len(s) == 1:
group[1].append(s)
continue
direction = getDirection(s[1], s[0])
if direction == 0:
res.append([s])
continue
for i in range(2, len(s)):
if getDirection(s[i], s[i-1]) != direction:
res.append([s])
continue
group[(len(s), direction)].append(s)
for k, v in group.items():
res.append(v)
return res