FilesExpand file tree

 master

/

FindAndReplacePattern890.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

87 lines (81 loc) · 2.7 KB

 master

/

FindAndReplacePattern890.java

Copy path

Top

File metadata and controls

• Code
• Blame

87 lines (81 loc) · 2.7 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

78

79

80

81

82

83

84

85

86

87

/**

* You have a list of words and a pattern, and you want to know which words in

* words matches the pattern.

*

* A word matches the pattern if there exists a permutation of letters p so

* that after replacing every letter x in the pattern with p(x), we get the

* desired word.

*

* (Recall that a permutation of letters is a bijection from letters to

* letters: every letter maps to another letter, and no two letters map to

* the same letter.)

*

* Return a list of the words in words that match the given pattern.

*

* You may return the answer in any order.

*

* Example 1:

* Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"

* Output: ["mee","aqq"]

* Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}.

* "ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,

* since a and b map to the same letter.

*

* Note:

* 1 <= words.length <= 50

* 1 <= pattern.length = words[i].length <= 20

*/

public class FindAndReplacePattern890 {

public List<String> findAndReplacePattern(String[] words, String pattern) {

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

char[] pat = pattern.toCharArray();

int N = pattern.length();

for (String word: words) {

if (isPermutation(word.toCharArray(), pat, N)) {

res.add(word);

}

}

return res;

}

public boolean isPermutation(char[] word, char[] pattern, int N) {

Map<Character, Character> map = new HashMap<>();

for (int i=0; i<N; i++) {

if (map.containsKey(word[i])) {

if (map.get(word[i]) != pattern[i]) return false;

} else {

if (map.values().contains(pattern[i])) return false;

map.put(word[i], pattern[i]);

}

}

return true;

}

public List<String> findAndReplacePattern2(String[] words, String pattern) {

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

int code = encode(pattern);

for (String w: words) {

if (code == encode(w)) {

res.add(w);

}

}

return res;

}

public int encode(String s) {

int res = 0;

char[] chars = s.toCharArray();

char first = chars[0];

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

map.put(0, 0);

int i = 1;

for (int j=0; j<chars.length; j++) {

int offset = chars[j] - first;

if (map.containsKey(offset)) {

res += map.get(offset) * j;

} else {

map.put(offset, i);

res += i * j;

i++;

}

}

return res;

}

}