Leetcode | Count Number of Texts | Java

devstromo · devstromo · commit 75e488a1a46b · 2025-05-04T19:16:14.000-03:00
diff --git a/leetcode/src/main/java/com/devstromo/medium/p2266/Solution.java b/leetcode/src/main/java/com/devstromo/medium/p2266/Solution.java
@@ -1,5 +1,8 @@
 package com.devstromo.medium.p2266;
 
+import java.util.ArrayList;
+import java.util.List;
+
 public class Solution {
     private static final int MOD = 1_000_000_007;
 
@@ -21,4 +24,63 @@ public int countTexts(String pressedKeys) {
 
         return dp[n];
     }
+
+    int mod = (int) 1e9 + 7;
+    int[] typeMap = new int[]{-1, -1, 0, 0, 0, 0, 0, 1, 0, 1};
+
+    public int countTextsBest(String pressedKeys) {
+        // left * right
+        List<int[]> list = new ArrayList<>();
+        int cnt = 0, max = 0;
+        char prev = '0';
+        for (char c : pressedKeys.toCharArray()) {
+            if (prev != c) {
+                if (prev != '0') list.add(new int[]{(prev - '0'), cnt});
+                max = Math.max(cnt, max);
+                cnt = 0;
+            }
+            cnt++;
+            prev = c;
+        }
+        if (cnt > 0) {
+            list.add(new int[]{(prev - '0'), cnt});
+            max = Math.max(max, cnt);
+        }
+
+        long res = 1;
+        Long[][] dp = new Long[2][max + 1];
+        dp[0][0] = 1l;
+        dp[1][0] = 1l;
+        for (int i = 0; i < list.size(); i++) {
+            int[] cur = list.get(i);
+            int num = cur[0], curCnt = cur[1];
+            int type = typeMap[num];
+
+            long combination = helper(type, curCnt, dp);
+
+            res = (res * combination) % mod;
+        }
+
+        return (int) res;
+    }
+
+    // type 0 = 3 char
+    // type 1 = 4 char
+    long helper(int type, int cnt, Long[][] dp) {
+        if (dp[type][cnt] != null) return dp[type][cnt];
+
+        for (int i = 1; i <= cnt; i++) {
+            if (dp[type][i] != null) continue;
+
+            if (i == 1) dp[type][i] = 1l;
+            if (i == 2) dp[type][i] = 2l;
+            if (i == 3) dp[type][i] = 4l;
+            // System.out.println(i + " dp[type][i-1]: "+ dp[type][i-1]);
+            if (i >= 4) {
+                if (type == 0) dp[type][i] = (dp[type][i - 1] + dp[type][i - 2] + dp[type][i - 3]) % mod;
+                else dp[type][i] = (dp[type][i - 1] + dp[type][i - 2] + dp[type][i - 3] + dp[type][i - 4]) % mod;
+            }
+        }
+        return dp[type][cnt];
+    }
 }
diff --git a/leetcode/src/test/java/com/devstromo/medium/p2266/SolutionUnitTest.java b/leetcode/src/test/java/com/devstromo/medium/p2266/SolutionUnitTest.java
@@ -13,6 +13,12 @@ class SolutionUnitTest {
     void testCountNumberOfTexts() {
         assertEquals(8, solution.countTexts("22233"));
         assertEquals(82876089, solution.countTexts("222222222222222222222222222222222222"));
+    }
 
+    @Test
+    @DisplayName("Test Count Number of Texts Best")
+    void testCountNumberOfTextsBest() {
+        assertEquals(8, solution.countTextsBest("22233"));
+        assertEquals(82876089, solution.countTextsBest("222222222222222222222222222222222222"));
     }
 }

Original file line number	Diff line number	Diff line change
`@@ -13,6 +13,12 @@ class SolutionUnitTest {`
`13`	`13`	`void testCountNumberOfTexts() {`
`14`	`14`	`assertEquals(8, solution.countTexts("22233"));`
`15`	`15`	`assertEquals(82876089, solution.countTexts("222222222222222222222222222222222222"));`
	`16`	`+ }`
`16`	`17`
	`18`	`+ @Test`
	`19`	`+ @DisplayName("Test Count Number of Texts Best")`
	`20`	`+ void testCountNumberOfTextsBest() {`
	`21`	`+ assertEquals(8, solution.countTextsBest("22233"));`
	`22`	`+ assertEquals(82876089, solution.countTextsBest("222222222222222222222222222222222222"));`
`17`	`23`	`}`
`18`	`24`	`}`