方法1: Brute Force
枚举所有的(nums[i], nums[j])组合，相加在和target比较。
时间复杂度：O(mn2) m为字符串的最长长度。
空间复杂度：O(m)
优化前 67ms, 49.3M
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int numOfPairs(vector<string>& nums, string target) { const int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (i != j && nums[i] + nums[j] == target) ++ans; return ans; } }; |
一些工程上的优化
- 用string_view作为参数类型，减少一次string copy
- 先比较长度，再判断内容。
- string_view.substr 是O(1)时间，和直接用strncmp比较内容是一样的。
优化后 3ms, 12.88MB
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: int numOfPairs(vector<string>& nums, string_view target) { const int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (i != j && nums[i].size() + nums[j].size() == target.size() && target.substr(0, nums[i].size()) == nums[i] && target.substr(nums[i].size()) == nums[j]) ++ans; return ans; } }; |