Skip to content

2266. Count Number of Texts 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  int countTexts(string pressedKeys) {
    constexpr int kMod = 1'000'000'007;
    const int n = pressedKeys.length();
    // dp[i] := # of possible text messages of s[i:]
    vector<long> dp(n + 1);
    dp[n] = 1;  // ""

    for (int i = n - 1; i >= 0; --i) {
      dp[i] = dp[i + 1];
      if (isSame(pressedKeys, i, 2))
        dp[i] += dp[i + 2];
      if (isSame(pressedKeys, i, 3))
        dp[i] += dp[i + 3];
      if ((pressedKeys[i] == '7' || pressedKeys[i] == '9') &&
          isSame(pressedKeys, i, 4))
        dp[i] += dp[i + 4];
      dp[i] %= kMod;
    }

    return dp[0];
  }

 private:
  // Returns true if s[i:i + k] are same chars
  bool isSame(const string& s, int i, int k) {
    if (i + k > s.length())
      return false;
    for (int j = i + 1; j < i + k; ++j)
      if (s[j] != s[i])
        return false;
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public int countTexts(String pressedKeys) {
    final int kMod = 1_000_000_007;
    final int n = pressedKeys.length();
    // dp[i] := # of possible text messages of s[i:]
    long[] dp = new long[n + 1];
    dp[n] = 1; // ""

    for (int i = n - 1; i >= 0; --i) {
      dp[i] = dp[i + 1];
      if (isSame(pressedKeys, i, 2))
        dp[i] += dp[i + 2];
      if (isSame(pressedKeys, i, 3))
        dp[i] += dp[i + 3];
      if ((pressedKeys.charAt(i) == '7' || pressedKeys.charAt(i) == '9') &&
          isSame(pressedKeys, i, 4))
        dp[i] += dp[i + 4];
      dp[i] %= kMod;
    }

    return (int) dp[0];
  }

  // Returns true if s[i:i + k] are same chars
  private boolean isSame(final String s, int i, int k) {
    if (i + k > s.length())
      return false;
    for (int j = i + 1; j < i + k; ++j)
      if (s.charAt(j) != s.charAt(i))
        return false;
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def countTexts(self, pressedKeys: str) -> int:
    kMod = 1_000_000_007
    n = len(pressedKeys)
    # dp[i] := # of possible text messages of s[i:]
    dp = [0] * n + [1]

    # Returns True if s[i:i + k] are same chars
    def isSame(s: str, i: int, k: int) -> bool:
      if i + k > len(s):
        return False
      for j in range(i + 1, i + k):
        if s[j] != s[i]:
          return False
      return True

    for i in reversed(range(n)):
      dp[i] = dp[i + 1]
      if isSame(pressedKeys, i, 2):
        dp[i] += dp[i + 2]
      if isSame(pressedKeys, i, 3):
        dp[i] += dp[i + 3]
      if (pressedKeys[i] == '7' or pressedKeys[i] == '9') and \
              isSame(pressedKeys, i, 4):
        dp[i] += dp[i + 4]
      dp[i] %= kMod

    return dp[0]