FilesExpand file tree

 master

/

ShortEncodingOfWords.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

62 lines (57 loc) · 1.8 KB

 master

/

ShortEncodingOfWords.java

Copy path

Top

File metadata and controls

• Code
• Blame

62 lines (57 loc) · 1.8 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

package hashing;

import java.util.*;

/**

* Created by gouthamvidyapradhan on 04/05/2018. Given a list of words, we may encode it by writing

* a reference string S and a list of indexes A.

*

* <p>For example, if the list of words is ["time", "me", "bell"], we can write it as S =

* "time#bell#" and indexes = [0, 2, 5].

*

* <p>Then for each index, we will recover the word by reading from the reference string from that

* index until we reach a "#" character.

*

* <p>What is the length of the shortest reference string S possible that encodes the given words?

*

* <p>Example:

*

* <p>Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes =

* [0, 2, 5]. Note:

*

* <p>1 <= words.length <= 2000. 1 <= words[i].length <= 7. Each word has only lowercase letters.

*

* <p>Solution: Sort the words by length and then use a hashmap to map each substring of a string

* with its position.

*/

public class ShortEncodingOfWords {

class Node {

String s;

int l;

Node(String s, int l) {

this.s = s;

this.l = l;

}

}

public static void main(String[] args) {

String[] A = {"memo", "me", "mo"};

System.out.println(new ShortEncodingOfWords().minimumLengthEncoding(A));

}

public int minimumLengthEncoding(String[] words) {

List<Node> list = new ArrayList<>();

for (String w : words) {

list.add(new Node(w, w.length()));

}

Collections.sort(list, (o1, o2) -> Integer.compare(o2.l, o1.l));

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

int count = 0;

for (Node node : list) {

String str = node.s;

if (!map.containsKey(str)) {

for (int i = 0, l = str.length(); i < l; i++) {

map.put(str.substring(i, l), count + i);

}

count += (str.length() + 1);

}

}

return count;

}

}