Leetcode: Multiply Strings (string)

PROBLEM:

https://leetcode.com/problems/multiply-strings/

--------------------------------------------------

The shorter one is set as multiplicand and then using the normal multiplication process shown above. To easily deal with the alingment in summation, reverse the multiplication results. In the end reverse the summation result. 

///////////////////////////////////////////////////////////////

//

class Solution {

public:

       string multiply(string num1, string num2) {

              vector<vector<int>> dig;

              int n1 = num1.size(), n2 = num2.size();

              string lg, sht;

              int iLong, iShort;

              //choose short one as multiplicand

              if (n1<n2){

                     lg = num2; sht = num1;

                     iLong = n2; iShort = n1;

              }

              else{

                     lg = num1; sht = num2;

                     iLong = n1; iShort = n2;

              }

              int count = 0;

              for (int i = iShort - 1; i>-1; i--){

                     int a = sht[i] - '0', c = 0;

                     vector<int> tmp;

                     tmp.resize(count, 0);

                     for (int j = iLong - 1; j>-1; j--){

                           int b = (lg[j] - '0')*a + c, rem = b % 10;

                           c = b / 10;

                           tmp.push_back(rem);

                     }

                     tmp.push_back(c);

                     tmp.resize(iLong + iShort, 0);//resize to the same length

                     dig.push_back(tmp);

                     count++;

              }

              //do summation

              vector<int> tmp1;

              unsigned long long c1 = 0, sum = 0;

              for (int k = 0; k<iLong + iShort; k++){

                     for (int m = 0; m<iShort; m++){

                           sum = sum + dig[m][k];

                     }

                     sum += c1;

                     int res = sum % 10;

                     tmp1.push_back(res);

                     c1 = sum / 10;

                     sum = 0;

              }

              // push back the c1

              while (c1>0){

                     tmp1.push_back(c1 % 10);

                     c1 = c1 / 10;

              }

              //restore the final string

              int l = iLong + iShort - 1;

              while (tmp1[l] == 0)l--;//

              string result;

              for (; l>-1; l--){

                     result.push_back(tmp1[l] + '0');

              }

              if (result.size() == 0) return "0";

              return result;

       }

};

Leetcode: Reverse Words in a String (8ms) (string)(two pointers)

PROBLEM:


https://leetcode.com/problems/reverse-words-in-a-string/


---------------------------------

Searching a word from right to left, using two pointers to mark the location of a word. using another string to temporally store the result.


/////////////////////////////////////////////////
//8ms

class Solution {

public:

       void reverseWords(string &s) {

              int n = s.size(), l = n - 1, r = n - 1;

              string res;

              while (l>-1){

                     int i = l;

                     //looking for non-space char

                     while (i>-1 && s[i] == ' ')i--;

                     r = i;

                     if (i == -1)break;//all leading char are ' '.

                     //looking for space. Note: put i>-1 ahead of s[i]!=' ';

                     while (i>-1 && s[i] != ' ')i--;

                     l = i + 1;

                     res.append(s, l, r - l + 1);

                     res.push_back(' ');

                     l = i - 1;

                     r = l;

              }

              //check input and check tmp result and remove final space

              if(n!=0 && res.size()!=0)res.erase(res.size()-1,1);

              s = res;

       }

};

Leetcode: Roman to Integer (36ms) (string)

PROBLEM:

https://leetcode.com/problems/roman-to-integer/


-----------------------------------------------------



1. How to read a Roman numbers? Please refer to following link:
http://4thgradecrocs.weebly.com/roman-numerals.html

  I=1   V=5    X=10   L=50   C=100   D=500   M=1000    

2. Basic idea is to read from right to left and :

if left one is >= the right one, use +
if left one is < the right one, use -

/////////////////////////////////////////////////////////////////////
//code 36ms

class Solution {

private:

       int r2n(char c){

              int res;

              switch (c){

              case 'I': res = 1; break;

              case 'V': res = 5; break;

              case 'X': res = 10; break;

              case 'L': res = 50; break;

              case 'C': res = 100; break;

              case 'D': res = 500; break;

              case 'M': res = 1000; break;

              default:;

              }

              return res;

       }

public:

       int romanToInt(string s) {

              int n = s.size(), res = r2n(s[n - 1]);

              //read from right to left

              for (int i = n - 2; i>-1; i--){

                     if (r2n(s[i + 1]) <= r2n(s[i]))res = res + r2n(s[i]);

                     else res = res - r2n(s[i]);

              }

              return res;

       }

};

Leetcode: String to Integer (atoi) (string)

PROBLEM:

https://leetcode.com/problems/string-to-integer-atoi/


---------------------------------


Basically the problem want to translate:
   "   +987778xw " 
into an integer.

Note:
1. limit check: INT_MAX, INT_MIN;
    the problem indicate the  INT_MAX (2147483647) or INT_MIN (-2147483648). the value 2147483647 is the limit of unsigned long long!! See below:

INT_MIN	Minimum value for an object of type int	-32767 (-215+1) or less*
INT_MAX	Maximum value for an object of type int	32767 (215-1) or greater*
UINT_MAX	Maximum value for an object of type unsigned int	65535 (216-1) or greater*
LONG_MIN	Minimum value for an object of type long int	-2147483647 (-231+1) or less*
LONG_MAX	Maximum value for an object of type long int	2147483647 (231-1) or greater*
ULONG_MAX	Maximum value for an object of type unsigned long int	4294967295 (232-1) or greater*

This confused me. 

2. 

//////////////////////////////////////////////////////

//code 12ms

class Solution {

public:

       int myAtoi(string str) {

              //pass the initial space

              int i = 0;

              unsigned long long res = 0;

              while (str[i] == ' ')i++;

              //parse the first non space char

              if (str[i] != '+' && str[i] != '-' && isdigit(str[i]) == 0)return 0;

              bool neg = false;

              if (str[i] == '+') { neg = false; i++; }

              else if (str[i] == '-') { neg = true; i++; }

              else neg = false;

              //parse the char followered by + -

              if (isdigit(str[i]) == 0)return 0;

              else {

                     while (isdigit(str[i])){

                           res = res * 10 + str[i] - '0';

                           if (res>INT_MAX)return neg ? INT_MIN : INT_MAX;

                           i++;

                     }

              }

              return neg ? -res : res;

       }

};

Leetcodes: Text Justification (0ms) (string)

PROBLEM:

https://leetcode.com/problems/text-justification/

---------------------------------------------------

A trivial string problem. Logic is not difficult, but it takes time to correctly code the problem.
1. fetch enough words;
2. compose the line: there are three kinds of line, namely
   one word line;
   last line;
   the other lines.



/////////////////////////////////////////////////////////
// codes

class Solution {

public:

       vector<string> fullJustify(vector<string>& words, int maxWidth) {

              vector<string> res;

              int len = words.size();

              //check input

              if (maxWidth == 0)return{ "" };

              //top loop

              for (int i = 0; i<words.size(); ){

                     int j = 0, wLen = 0, sLen = 0;

                     while (i + j<len){

                           wLen += words[i + j].size();

                           if (j + 1 >= 2)sLen = j + 1 - 2 + 1;//space

                           if (wLen + sLen>maxWidth){

                                  wLen -= words[i + j].size();

                                  j--;

                                  break;

                           }

                           else if (i + j == len - 1)break;

                           j++;

                     }

                     string tmp;

                     //compose the line

                     //only one word

                     if (j == 0){

                           tmp = words[i + j];

                           tmp.resize(maxWidth, ' ');

                           res.push_back(tmp);

                     }

                     //last line

                     else if (i + j == words.size()-1){

                           for (int k = i; k<i + j + 1; k++){

                                  tmp.append(words[k]);

                                  tmp.push_back(' ');

                           }

                           tmp.resize(maxWidth, ' ');

                           res.push_back(tmp);

                     }

                     //others

                     else{

                           sLen = maxWidth - wLen;

                           int sMod = sLen%j, sDiv = sLen / j;

                int count = sMod;

                            for (int k = i; k<i+j + 1; k++){

                                  tmp.append(words[k]);

                                  //more space appended

                                  if (count!=0){

                                         string space(1 + sDiv, ' ');

                                         tmp.append(space);

                                         count--;

                                  }

                                  //less space appended

                                  else{

                                         string space(sDiv, ' ');

                                         tmp.append(space);

                                  }

                           }

                           tmp.resize(maxWidth);//remove the last extra spaces

                           res.push_back(tmp);

                     }

            i = i + j + 1;

              }

       return res;

}

};