In this guide, you will get 2266. Count Number of Texts LeetCode Solution with the best time and space complexity. The solution to Count Number of Texts problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Alice is texting Bob using her phone. The mapping of digits to letters is shown in the figure below.
In order to add a letter, Alice has to press the key of the corresponding digit i times, where i is the position of the letter in the key.
For example, to add the letter ‘s’, Alice has to press ‘7’ four times. Similarly, to add the letter ‘k’, Alice has to press ‘5’ twice.
Note that the digits ‘0’ and ‘1’ do not map to any letters, so Alice does not use them.
However, due to an error in transmission, Bob did not receive Alice’s text message but received a string of pressed keys instead.
For example, when Alice sent the message “bob”, Bob received the string “2266622”.
Given a string pressedKeys representing the string received by Bob, return the total number of possible text messages Alice could have sent.
Since the answer may be very large, return it modulo 109 + 7.
Input: pressedKeys = “22233”
Output: 8
Explanation:
The possible text messages Alice could have sent are:
“aaadd”, “abdd”, “badd”, “cdd”, “aaae”, “abe”, “bae”, and “ce”.
Since there are 8 possible messages, we return 8.
Example 2:
Input: pressedKeys = “222222222222222222222222222222222222”
Output: 82876089
Explanation:
There are 2082876103 possible text messages Alice could have sent.
Since we need to return the answer modulo 109 + 7, we return 2082876103 % (109 + 7) = 82876089.
Constraints:
1 <= pressedKeys.length <= 105
pressedKeys only consists of digits from '2' – '9'.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2266. Count Number of Texts LeetCode Solution in C++
class Solution {
public:
int countTexts(string pressedKeys) {
constexpr int kMod = 1'000'000'007;
const int n = pressedKeys.length();
// dp[i] := the number of possible text messages of pressedKeys[i..n)
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 the same digits.
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;
}
}; /* code provided by PROGIEZ */
2266. Count Number of Texts LeetCode Solution in Java
class Solution {
public int countTexts(String pressedKeys) {
final int kMod = 1_000_000_007;
final int n = pressedKeys.length();
// dp[i] := the number of possible text messages of pressedKeys[i..n)
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 the same digits.
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;
}
} // code provided by PROGIEZ
2266. Count Number of Texts LeetCode Solution in Python
class Solution:
def countTexts(self, pressedKeys: str) -> int:
kMod = 1_000_000_007
n = len(pressedKeys)
# dp[i] := the number of possible text messages of pressedKeys[i..n)
dp = [0] * n + [1]
def isSame(s: str, i: int, k: int) -> bool:
"""Returns True if s[i..i + k) are the same digits."""
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] # code by PROGIEZ
