FilesExpand file tree

 master

/

GroupShiftedStrings249.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

77 lines (72 loc) · 2.37 KB

 master

/

GroupShiftedStrings249.java

Copy path

Top

File metadata and controls

• Code
• Blame

77 lines (72 loc) · 2.37 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Given a string, we can "shift" each of its letter to its successive letter,

* for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:

*

* "abc" -> "bcd" -> ... -> "xyz"

* Given a list of strings which contains only lowercase alphabets, group all

* strings that belong to the same shifting sequence.

*

* Example:

*

* Input: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],

* Output:

* [

* ["abc","bcd","xyz"],

* ["az","ba"],

* ["acef"],

* ["a","z"]

* ]

*/

public class GroupShiftedStrings249 {

public List<List<String>> groupStrings(String[] strings) {

Map<String, List<String>> map = new HashMap<>();

for (String s: strings) {

boolean found = false;

for (String k: map.keySet()) {

if (s.length() != k.length()) continue;

boolean b = true;

int diff = getDiff(s.charAt(0), k.charAt(0));

for (int i=1; i<s.length(); i++) {

b = getDiff(s.charAt(i), k.charAt(i)) == diff;

if (!b) break;

}

if (b) {

map.get(k).add(s);

found = true;

break;

}

}

if (!found) {

List<String> tmp = new ArrayList<>();

tmp.add(s);

map.put(s, tmp);

}

}

return new ArrayList<List<String>>(map.values());

}

private int getDiff(char c1, char c2) {

int init = c1 - c2;

while (init < 0) {

init += 26;

}

return init;

}

/**

* https://leetcode.com/problems/group-shifted-strings/discuss/127090/Short-Java-solution

*/

public List<List<String>> groupStrings2(String[] strings) {

Map<String, List<String>> groups = new HashMap<String, List<String>>();

for (String s : strings) {

int shift = 'z' - s.charAt(0);

StringBuilder sb = new StringBuilder();

for (int i = 0; i < s.length(); i++) {

sb.append((s.charAt(i) + shift) % 26);

}

if (!groups.containsKey(sb.toString())) {

groups.put(sb.toString(), new ArrayList<String>());

}

groups.get(sb.toString()).add(s);

}

return new ArrayList<List<String>>(groups.values());

}

}