Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/408.html
408. Valid Word Abbreviation (Easy)
Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.
A string such as "word" contains only the following valid abbreviations:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
Notice that only the above abbreviations are valid abbreviations of the string "word". Any other string is not a valid abbreviation of "word".
Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.
Example 1:
Given s = "internationalization", abbr = "i12iz4n": Return true.
Example 2:
Given s = "apple", abbr = "a2e": Return false.
Companies:
Facebook
Related Topics:
String
Similar Questions:
Solution 1.
// OJ: https://leetcode.com/problems/valid-word-abbreviation/
// Time: O(M+N)
// Space: O(1)
class Solution {
public:
bool validWordAbbreviation(string word, string abbr) {
int i = 0, j = 0, M = word.size(), N = abbr.size();
while (i < M && j < N) {
if (isalpha(abbr[j])) {
if (word[i] != abbr[j]) return false;
++i;
++j;
continue;
}
int len = 0;
while (j < N && isdigit(abbr[j])) {
len = 10 * len + (abbr[j++] - '0');
if (!len) return false;
}
i += len;
}
return i == M && j == N;
}
};
-
class Solution { public boolean validWordAbbreviation(String word, String abbr) { List<String> abbrList = new ArrayList<String>(); StringBuffer sb = new StringBuffer(); int abbrLength = abbr.length(); for (int i = 0; i < abbrLength; i++) { char c = abbr.charAt(i); if (c >= 'A') { if (sb.length() > 0) { abbrList.add(sb.toString()); sb = new StringBuffer(); } abbrList.add(String.valueOf(c)); } else sb.append(c); } if (sb.length() > 0) abbrList.add(sb.toString()); int wordLength = word.length(); int abbrListLength = abbrList.size(); int wordIndex = 0; int abbrIndex = 0; while (wordIndex < wordLength && abbrIndex < abbrListLength) { String curAbbr = abbrList.get(abbrIndex); if (curAbbr.charAt(0) >= 'A') { char abbrChar = curAbbr.charAt(0); char c = word.charAt(wordIndex); if (abbrChar != c) return false; else { wordIndex++; abbrIndex++; } } else { if (curAbbr.charAt(0) == '0') return false; int skip = Integer.parseInt(curAbbr); wordIndex += skip; abbrIndex++; } } return wordIndex == wordLength && abbrIndex == abbrListLength; } } -
// OJ: https://leetcode.com/problems/valid-word-abbreviation/ // Time: O(M+N) // Space: O(1) class Solution { public: bool validWordAbbreviation(string word, string abbr) { int i = 0, j = 0, M = word.size(), N = abbr.size(); while (i < M && j < N) { if (isalpha(abbr[j])) { if (word[i] != abbr[j]) return false; ++i; ++j; continue; } int len = 0; while (j < N && isdigit(abbr[j])) { len = 10 * len + (abbr[j++] - '0'); if (!len) return false; } i += len; } return i == M && j == N; } }; -
class Solution: def validWordAbbreviation(self, word: str, abbr: str) -> bool: i = j = 0 m, n = len(word), len(abbr) while i < m: if j >= n: return False if word[i] == abbr[j]: i, j = i + 1, j + 1 continue k = j while k < n and abbr[k].isdigit(): k += 1 t = abbr[j:k] if not t.isdigit() or t[0] == '0' or int(t) == 0: return False i += int(t) j = k return i == m and j == n ############ class Solution(object): def validWordAbbreviation(self, dest, src): """ :type word: str :type abbr: str :rtype: bool """ start = j = 0 digit = False for i in range(0, len(src)): if src[i].isdigit(): if not digit: if src[i] == "0": return False start = i digit = True else: if digit: jump = int(src[start:i]) digit = False j += jump if j >= len(dest) or src[i] != dest[j]: return False j += 1 if i == len(src) - 1: if digit: jump = int(src[start:i + 1]) digit = False j += jump if j != len(dest): return False return True