|
1 | 1 | classSolution { |
2 | 2 | public: |
3 | | - vector<vector<int>> res; |
4 | | - |
5 | | - vector<vector<int>>fourSum(vector<int>& nums,int target) { |
6 | | - |
7 | | -if(nums.size() <4)return res; |
8 | | - |
9 | | - vector<int>quad; |
10 | | -sort(nums.begin() , nums.end()); |
11 | | -kSum(0,4,target,nums,quad); |
12 | | -return res; |
13 | | - } |
14 | | - |
15 | | - |
16 | | -voidkSum (int index ,int k ,longlong target, vector<int> nums , vector<int>&q) |
17 | | - { |
18 | | - |
19 | | -if(k ==2) |
20 | | - { |
21 | | -twoSum(index , target, q , nums); |
22 | | -return; |
23 | | - } |
24 | | - |
25 | | -for(int i = index ; i < nums.size() - k +1; i++) |
26 | | - { |
27 | | -if(i > index && nums[i] == nums[i-1])continue; |
28 | | - q.push_back(nums[i]); |
29 | | -kSum(i+1 , k-1 , target-nums[i] , nums , q); |
30 | | - q.pop_back(); |
31 | | - } |
32 | | - |
33 | | - } |
34 | | - |
35 | | -voidtwoSum (int start,longlong target,vector<int>&ans,vector<int>& nums) |
36 | | - { |
37 | | -int lo = start; |
38 | | -int hi = nums.size()-1; |
39 | | - |
40 | | -while(lo < hi) |
41 | | - { |
42 | | -int sum = nums[lo]+nums[hi]; |
43 | | -if(sum > target) hi--; |
44 | | -elseif (sum < target) lo++; |
45 | | - |
46 | | -else |
47 | | - { |
48 | | - ans.insert(ans.end() , {nums[lo] , nums[hi]}); |
49 | | - res.push_back(ans); |
| 3 | + stringlongestCommonPrefix(vector<string>& strs) { |
| 4 | + string result = strs[0]; |
| 5 | +int charIndex =0; |
50 | 6 |
|
51 | | - ans.pop_back(); |
52 | | - ans.pop_back(); |
53 | | - |
54 | | - lo++; |
55 | | -while (lo < hi && nums[lo] == nums[lo -1]) lo++; |
56 | | - } |
57 | | - } |
58 | | - } |
| 7 | +//finding minimum string length - that could be max common prefix |
| 8 | +long maxCharIndex = strs[0].length(); |
| 9 | +for (int i =1; i < strs.size(); ++i) { |
| 10 | +if (strs[i].length() < maxCharIndex) { |
| 11 | + maxCharIndex = strs[i].length(); |
| 12 | + } |
| 13 | + } |
| 14 | + |
| 15 | +while (charIndex < maxCharIndex) { |
| 16 | +char prevChar = strs[0][charIndex]; |
| 17 | +for (int i =1; i < strs.size(); ++i) { |
| 18 | +if (prevChar == strs[i][charIndex]) { |
| 19 | +continue; |
| 20 | + } |
| 21 | +return result.substr(0, charIndex); |
| 22 | + } |
| 23 | + ++charIndex; |
| 24 | + result += prevChar; |
| 25 | + } |
| 26 | +return result.substr(0, charIndex); |
| 27 | + } |
59 | 28 | }; |