New Problem Solution - "1813. Sentence Similarity III"

haoel · haoel · commit 1ab937ea7ac0 · 2021-04-06T12:50:12.000+08:00
diff --git a/README.md b/README.md
@@ -13,6 +13,7 @@ LeetCode
 |1818|[Minimum Absolute Sum Difference](https://leetcode.com/problems/minimum-absolute-sum-difference/) | [C++](./algorithms/cpp/minimumAbsoluteSumDifference/MinimumAbsoluteSumDifference.cpp)|Medium|
 |1817|[Finding the Users Active Minutes](https://leetcode.com/problems/finding-the-users-active-minutes/) | [C++](./algorithms/cpp/findingTheUsersActiveMinutes/FindingTheUsersActiveMinutes.cpp)|Medium|
 |1816|[Truncate Sentence](https://leetcode.com/problems/truncate-sentence/) | [C++](./algorithms/cpp/truncateSentence/TruncateSentence.cpp)|Easy|
+|1813|[Sentence Similarity III](https://leetcode.com/problems/sentence-similarity-iii/) | [C++](./algorithms/cpp/sentenceSimilarity/SentenceSimilarity.III.cpp)|Medium|
 |1812|[Determine Color of a Chessboard Square](https://leetcode.com/problems/determine-color-of-a-chessboard-square/) | [C++](./algorithms/cpp/determineColorOfAChessboardSquare/DetermineColorOfAChessboardSquare.cpp)|Easy|
 |1808|[Maximize Number of Nice Divisors](https://leetcode.com/problems/maximize-number-of-nice-divisors/) | [C++](./algorithms/cpp/maximizeNumberOfNiceDivisors/MaximizeNumberOfNiceDivisors.cpp)|Hard|
 |1807|[Evaluate the Bracket Pairs of a String](https://leetcode.com/problems/evaluate-the-bracket-pairs-of-a-string/) | [C++](./algorithms/cpp/evaluateTheBracketPairsOfAString/EvaluateTheBracketPairsOfAString.cpp)|Medium|
diff --git a/algorithms/cpp/sentenceSimilarity/SentenceSimilarity.III.cpp b/algorithms/cpp/sentenceSimilarity/SentenceSimilarity.III.cpp
@@ -0,0 +1,97 @@
+// Source : https://leetcode.com/problems/sentence-similarity-iii/
+// Author : Hao Chen
+// Date   : 2021-04-06
+
+/***************************************************************************************************** 
+ *
+ * A sentence is a list of words that are separated by a single space with no leading or trailing 
+ * spaces. For example, "Hello World", "HELLO", "hello world hello world" are all sentences. Words 
+ * consist of only uppercase and lowercase English letters.
+ * 
+ * Two sentences sentence1 and sentence2 are similar if it is possible to insert an arbitrary sentence 
+ * (possibly empty) inside one of these sentences such that the two sentences become equal. For 
+ * example, sentence1 = "Hello my name is Jane" and sentence2 = "Hello Jane" can be made equal by 
+ * inserting "my name is" between "Hello" and "Jane" in sentence2.
+ * 
+ * Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. 
+ * Otherwise, return false.
+ * 
+ * Example 1:
+ * 
+ * Input: sentence1 = "My name is Haley", sentence2 = "My Haley"
+ * Output: true
+ * Explanation: sentence2 can be turned to sentence1 by inserting "name is" between "My" and "Haley".
+ * 
+ * Example 2:
+ * 
+ * Input: sentence1 = "of", sentence2 = "A lot of words"
+ * Output: false
+ * Explanation: No single sentence can be inserted inside one of the sentences to make it equal to the 
+ * other.
+ * 
+ * Example 3:
+ * 
+ * Input: sentence1 = "Eating right now", sentence2 = "Eating"
+ * Output: true
+ * Explanation: sentence2 can be turned to sentence1 by inserting "right now" at the end of the 
+ * sentence.
+ * 
+ * Example 4:
+ * 
+ * Input: sentence1 = "Luky", sentence2 = "Lucccky"
+ * Output: false
+ * 
+ * Constraints:
+ * 
+ * 	1 <= sentence1.length, sentence2.length <= 100
+ * 	sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces.
+ * 	The words in sentence1 and sentence2 are separated by a single space.
+ ******************************************************************************************************/
+
+class Solution {
+private:
+    bool isWord(char ch) {
+        return (ch >='a' && ch <= 'z' ) || ( ch >='A' && ch <= 'Z');
+    }
+    bool isSpace(char ch) {
+        return (ch == ' ');
+    }
+    void split(string& s, vector<string>& words) {
+        s += ' ';
+        int start=0, end=0;
+        while(start < s.size()) {
+            while(isSpace(s[start])) start++;
+            end = start;
+            while(!isSpace(s[end])) end++;
+            words.push_back(s.substr(start, end-start));
+            start = end + 1;
+        }
+    }
+    void print(vector<string>& v) {
+        cout << "[";
+        for(int i=0; i<v.size()-1; i++) {
+            cout << v[i] << ", ";
+        }
+        cout << v[v.size()-1] << "]" << endl;
+    }
+public:
+    bool areSentencesSimilar(string sentence1, string sentence2) {
+        string& longstr = sentence1.size() >= sentence2.size() ? sentence1 : sentence2;
+        string& shortstr = sentence1.size() < sentence2.size() ? sentence1 : sentence2;
+        if ( longstr == shortstr ) return true;
+        
+        vector<string> words1, words2;
+        split(shortstr, words1);
+        split(longstr, words2);
+        //print(words1); print(words2);
+        
+        int left=0, right=words1.size()-1;
+        while(left< words1.size() && words1[left] == words2[left]) left++;
+        
+        int delta = words2.size() - words1.size();
+        while(right>=left && words1[right] == words2[delta+right]) right--;
+        //cout << left << ":" << right << ":" << delta << endl;
+        
+        return left > right;
+    }
+};
