|
3 | 3 | importjava.util.HashMap; |
4 | 4 | importjava.util.Map; |
5 | 5 |
|
6 | | -/** |
7 | | - * 953. Verifying an Alien Dictionary |
8 | | - * |
9 | | - * In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. |
10 | | - * |
11 | | - * Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language. |
12 | | - * |
13 | | - * Example 1: |
14 | | - * |
15 | | - * Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" |
16 | | - * Output: true |
17 | | - * Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted. |
18 | | - * |
19 | | - * Example 2: |
20 | | - * |
21 | | - * Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" |
22 | | - * Output: false |
23 | | - * Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted. |
24 | | - * |
25 | | - * Example 3: |
26 | | - * |
27 | | - * Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" |
28 | | - * Output: false |
29 | | - * Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info). |
30 | | - * |
31 | | - * |
32 | | - * Note: |
33 | | - * 1 <= words.length <= 100 |
34 | | - * 1 <= words[i].length <= 20 |
35 | | - * order.length == 26 |
36 | | - * All characters in words[i] and order are english lowercase letters. |
37 | | - */ |
38 | 6 | publicclass_953 { |
39 | | -publicstaticclassSolution1 { |
40 | | -publicbooleanisAlienSorted(String[]words,Stringorder) { |
41 | | -if (words.length ==1) { |
42 | | -returntrue; |
43 | | - } |
| 7 | +publicstaticclassSolution1 { |
| 8 | +publicbooleanisAlienSorted(String[]words,Stringorder) { |
| 9 | +if (words.length ==1) { |
| 10 | +returntrue; |
| 11 | +} |
44 | 12 |
|
45 | | -Map<Character,Integer>map =newHashMap<>(); |
46 | | -for (inti =0;i <order.length();i++) { |
47 | | -map.put(order.charAt(i),i); |
48 | | - } |
| 13 | +Map<Character,Integer>map =newHashMap<>(); |
| 14 | +for (inti =0;i <order.length();i++) { |
| 15 | +map.put(order.charAt(i),i); |
| 16 | +} |
49 | 17 |
|
50 | | -for (inti =0;i <words.length -1;i++) { |
51 | | -StringfirstWord =words[i]; |
52 | | -StringsecondWord =words[i +1]; |
53 | | -if (!sorted(firstWord,secondWord,map)) { |
54 | | -returnfalse; |
| 18 | +for (inti =0;i <words.length -1;i++) { |
| 19 | +StringfirstWord =words[i]; |
| 20 | +StringsecondWord =words[i +1]; |
| 21 | +if (!sorted(firstWord,secondWord,map)) { |
| 22 | +returnfalse; |
| 23 | + } |
| 24 | + } |
| 25 | +returntrue; |
55 | 26 | } |
56 | | - } |
57 | | -returntrue; |
58 | | - } |
59 | 27 |
|
60 | | -privatebooleansorted(StringfirstWord,StringsecondWord,Map<Character,Integer>map) { |
61 | | -for (inti =0;i <Math.min(firstWord.length(),secondWord.length());i++) { |
62 | | -if (firstWord.charAt(i) ==secondWord.charAt(i)) { |
63 | | -continue; |
64 | | - }else { |
65 | | -if (map.get(firstWord.charAt(i)) >map.get(secondWord.charAt(i))) { |
66 | | -returnfalse; |
67 | | - }else { |
68 | | -returntrue; |
69 | | - } |
| 28 | +privatebooleansorted(StringfirstWord,StringsecondWord,Map<Character,Integer>map) { |
| 29 | +for (inti =0;i <Math.min(firstWord.length(),secondWord.length());i++) { |
| 30 | +if (firstWord.charAt(i) ==secondWord.charAt(i)) { |
| 31 | +continue; |
| 32 | + }else { |
| 33 | +if (map.get(firstWord.charAt(i)) >map.get(secondWord.charAt(i))) { |
| 34 | +returnfalse; |
| 35 | + }else { |
| 36 | +returntrue; |
| 37 | + } |
| 38 | + } |
| 39 | + } |
| 40 | +returnfirstWord.length() <=secondWord.length(); |
70 | 41 | } |
71 | | - } |
72 | | -returnfirstWord.length() <=secondWord.length(); |
73 | 42 | } |
74 | | - } |
75 | 43 | } |