aboutsummaryrefslogtreecommitdiff
path: root/verify_alien_dict.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /verify_alien_dict.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'verify_alien_dict.cpp')
-rw-r--r--verify_alien_dict.cpp42
1 files changed, 42 insertions, 0 deletions
diff --git a/verify_alien_dict.cpp b/verify_alien_dict.cpp
new file mode 100644
index 0000000..009ac52
--- /dev/null
+++ b/verify_alien_dict.cpp
@@ -0,0 +1,42 @@
+// 953. Verifying an Alien Dictionary
+#include "leetcode.h"
+
+/*
+ * in an alien language, they also use english lowercase letters but in
+ * different 'order'. the 'order' of the alphabet is some permutation of
+ * lowercase letters. given a sequence of 'words' written in the alien language,
+ * and the 'order' of the alphabet, return 1 if and only if the given 'words'
+ * are sorted lexicographically in this alien language.
+ */
+
+class Solution {
+public:
+ bool isAlienSorted(vector<string> &words, string order) {
+ size_t indices[26]{};
+ for (size_t i = 0; i < order.size(); ++i)
+ indices[order[i] - 'a'] = i;
+ return is_sorted(words.begin(), words.end(),
+ [&indices](const string &w1, const string &w2) {
+ auto l1 = w1.size(), l2 = w2.size();
+ for (auto i = 0; i < min(l1, l2); ++i) {
+ auto c1 = w1[i], c2 = w2[i];
+ if (c1 != c2)
+ return indices[c1 - 'a'] < indices[c2 - 'a'];
+ }
+ return l1 < l2;
+ });
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<string> words1 = {"hello", "leetcode"};
+ vector<string> words2 = {"word", "world", "row"};
+ vector<string> words3 = {"apple", "app"};
+ cout << obj.isAlienSorted(words1, "hlabcdefgijkmnopqrstuvwxyz")
+ << endl; // expect: 1
+ cout << obj.isAlienSorted(words2, "worldabcefghijkmnpqstuvxyz")
+ << endl; // expect: 0
+ cout << obj.isAlienSorted(words3, "abcdefghijklmnopqrstuvwxyz")
+ << endl; // expect: 0
+}