FilesExpand file tree

 master

/

205_IsomorphicStrings205.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

105 lines (92 loc) · 2.84 KB

 master

/

205_IsomorphicStrings205.java

Copy path

Top

File metadata and controls

• Code
• Blame

105 lines (92 loc) · 2.84 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

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

/**

* Given two strings s and t, determine if they are isomorphic.

*

* Two strings are isomorphic if the characters in s can be replaced to get t.

*

* All occurrences of a character must be replaced with another character

* while preserving the order of characters. No two characters may map to the

* same character but a character may map to itself.

*

* Example 1:

* Input: s = "egg", t = "add"

* Output: true

*

* Example 2:

* Input: s = "foo", t = "bar"

* Output: false

*

* Example 3:

* Input: s = "paper", t = "title"

* Output: true

*

* Note:

* You may assume both s and t have the same length.

*/

public class IsomorphicStrings205 {

public boolean isIsomorphic(String s, String t) {

if (s == null && t == null) return true;

if (s == null || t == null || s.length() != t.length()) return false;

int N = s.length();

char[] charS = s.toCharArray();

char[] charT = t.toCharArray();

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

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

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

if (map.get(charS[i]) != charT[i]) return false;

} else {

if (map.values().contains(charT[i])) {

return false;

} else {

map.put(charS[i], charT[i]);

}

}

}

return true;

}

public boolean isIsomorphic2(String s1, String s2) {

int[] m = new int[512];

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

if (m[s1.charAt(i)] != m[s2.charAt(i)+256]) return false;

m[s1.charAt(i)] = m[s2.charAt(i)+256] = i+1;

}

return true;

}

public boolean isIsomorphic3(String sString, String tString) {

char[] s = sString.toCharArray();

char[] t = tString.toCharArray();

int length = s.length;

if(length != t.length) return false;

char[] sm = new char[256];

char[] tm = new char[256];

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

char sc = s[i];

char tc = t[i];

if(sm[sc] == 0 && tm[tc] == 0){

sm[sc] = tc;

tm[tc] = sc;

}else{

if(sm[sc] != tc || tm[tc] != sc){

return false;

}

}

}

return true;

}

public boolean isIsomorphic4(String sString, String tString) {

return encode(sString.toCharArray()) == encode(tString.toCharArray());

}

private int encode(char[] chars) {

int[] map = new int[256];

int res = 0;

int id = 1;

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

char ch = chars[i-1];

if (map[ch] == 0) {

map[ch] = id;

id++;

}

res += map[ch] * i;

}

return res;

}

}