【LeetCode】65. Valid Number

题目描述

Validate if a given string is numeric.

Some examples:

"0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

解题思路

可以大概结合一下编译原理中的上下文无关文法。 大概可以有如下的规则

exponent -> float + 'e' + int float -> int + '.' + int | int int -> +DIGITS | -DIGITS | DIGITS DIGITS -> {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

先将string两边的空格全部strip掉，然后利用上面的规则进行判断。 上面的规则不能覆盖得很完全。还需要仔细处理一些边界情况。 总共1500多个测例，要是不能run code并且wrong answer没有任何提示的话，想AC估计得很仔细……

AC代码

class Solution { public: bool isInt(string s, bool flag = true) { for (int i = 0; i < s.size(); ++i) { //detect "+1" as true while "+" as false if (flag && i == 0 && s.size() > 1 && (s[i] == '-' || s[i] == '+')) continue; if (!(s[i] >= '0' && s[i] <= '9')) return false; } return true; } bool isFloat(string s) { int pIdx = 0; for (; pIdx < s.size(); ++pIdx) { if (s[pIdx] == '.') break; } if (pIdx >= s.size()) return isInt(s); string leftS = s.substr(0, pIdx); string rightS = s.substr(pIdx + 1, s.size() - pIdx - 1); // detect "." as false if (leftS == "" && rightS == "") return false; // detect "+.1" as true if ((leftS == "+" || leftS == "-") && rightS != "") return isInt(rightS, false); return isInt(leftS) && isInt(rightS, false); } string strip(string s) { int startIdx = 0; for (;startIdx < s.size() - 1; ++startIdx) { if (s[startIdx] != ' ') break; } if (startIdx >= s.size()) return ""; int endIdx = s.size() - 1; for (; endIdx > startIdx; --endIdx) { if (s[endIdx] != ' ') break; } return s.substr(startIdx, endIdx - startIdx + 1); } bool isNumber(string s) { s = strip(s); //find e int i = 0; for (; i < s.size(); ++i) { if (s[i] == 'e') break; } if (i >= s.size()) return isFloat(s); if (i == 0 || i == s.size() - 1) return false; string leftS = s.substr(0, i); string rightS = s.substr(i + 1, s.size() - i - 1); return isFloat(leftS) && isInt(rightS); } };