added solution and test case for 809 (fishercoder1534#149)

ashmichheda · web-flow · commit cb0df7250d7c · 2021-01-16T09:49:17.000-08:00
diff --git a/README.md b/README.md
@@ -385,6 +385,7 @@ _If you like this project, please leave me a star._ &#9733;
 |819|[Most Common Word](https://leetcode.com/problems/most-common-word/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_819.java) |  |Easy| HashMap
 |814|[Binary Tree Pruning](https://leetcode.com/problems/binary-tree-pruning/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_814.java) |  |Medium| recursion, DFS 
 |811|[Subdomain Visit Count](https://leetcode.com/problems/subdomain-visit-count/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_811.java) | |Easy| HashMap
+|809|[Expressive Words](https://leetcode.com/problems/expressive-words/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_809.java) | |Medium|
 |807|[Max Increase to Keep City Skyline](https://leetcode.com/problems/max-increase-to-keep-city-skyline/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_807.java) | |Medium|
 |806|[Number of Lines To Write String](https://leetcode.com/problems/number-of-lines-to-write-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_806.java) |  |Easy|
 |804|[Unique Morse Code Words](https://leetcode.com/problems/unique-morse-code-words/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_804.java) |  |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_809.java b/src/main/java/com/fishercoder/solutions/_809.java
@@ -0,0 +1,64 @@
+package com.fishercoder.solutions;
+
+public class _809 {
+    public static class Solution1 {
+        public int expressiveWords (String S, String[] words ) {
+            int ans = 0;
+            for (String w : words) {
+                if (check(S, w)) {
+                    ans++;
+                }
+            }
+            return ans;
+        }
+        private boolean check (String S, String w) {
+            int i = 0;
+            int j = 0;
+            /* Logic is to check whether character at same index of S and w are same
+               if same,
+                1. Find the consecutive number of occurrences of the char in S (say len1) and w ( say len2)
+                2. If len1 == len 2 , move to the next char in S and w
+                3. If  len1 >= 3 and len2 < len1, means we can make the char in w stretchy to match len1
+                4. else, return false, because it's not possible to stretch the char in w
+             */
+            while (i < S.length() && j < w.length()) {
+                char ch1 = S.charAt(i);
+                char ch2 = w.charAt(j);
+                
+                int len1 = getLen(S, i);
+                int len2 = getLen(w, j);
+                if (ch1 == ch2) {
+                    if (len1 == len2) {
+                        i = i + len1;
+                        j = j + len2;
+                    }
+                    else if (len1 >= 3 && len2 < len1) {
+                        i = i + len1;
+                        j = j + len2;
+                    }
+                    else {
+                        return false;
+                    }
+                }
+                else {
+                    return false;
+                }
+            }
+            return i == S.length() && j == w.length();
+        }
+
+        private int getLen (String value, int i) {
+            i = i + 1;
+            int count = 1;
+            for(int j = i; j<value.length(); j++) {
+                if(value.charAt(j) == value.charAt(i-1)) {
+                    count++;
+                }
+                else {
+                    break;
+                }
+            }
+            return count;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_809Test.java b/src/test/java/com/fishercoder/_809Test.java
@@ -0,0 +1,25 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._809;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static junit.framework.TestCase.assertEquals;
+
+public class _809Test {
+    private static _809.Solution1 solution1;
+    private String[] words;
+    private String S;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _809.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        words = new String[] {"hello", "hi", "helo"};
+        S = "heeellooo";
+        assertEquals(1, solution1.expressiveWords(S, words));
+    }
+}
