## Tuesday, April 21, 2015

### LeetCode OJ - Largest Number

Problem:

Solution:

Apparently we wanted to use sorting, but how do we know if one string A should goes before string B?

First consider the case when A is not a prefix of B and B is not a prefix of A, this case is easy. Just do lexicographical order for these two strings. If A is lexicographically ordered after B, then A should goes before B.

An example would be 57 should order before 55, or 444. This is obvious.

Things become tricky if A is a prefix of B. Now it is possible both ways.

Let say A is 12, and B is 123, we have B should goes before A case, the answer is 12312.
Let say A is 12, and B is 121, we have A should goes before B case, the answer is 12121

How should we reconcile this? Consider a special case 3 and 34, we can tell immediately that 34 should goes before 3 because 4 is before 3.

Denote the string B be the concatenation of AB' - it looks like we can tell if A or B should goes first by comparing A and B' - this is the key insight!

Suppose B' should goes before A, then AB'A is better than AAB', so AB' should goes before A.
Suppose A should goes before B', then AAB' is better than AB'A, so A should goes before AB'.

The only case that we cannot tell is when the strings are identical. That correspond to the case that the strings are in fact cannot be compared. Interesting scenario such as 1212 cannot be ordered with 121212, in that case, just pick an arbitrary one will work.

With that, we conclude the exercise with the simple code as follow.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/largest-number/

#include "LEET_LARGEST_NUMBER.h"
#include <list>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_LARGEST_NUMBER
{
bool isBefore(string a, string b)
{
for (unsigned int i = 0; i < a.length() && i < b.length(); i++)
{
if (a[i] < b[i])
{
return false;
}
else if (a[i] > b[i])
{
return true;
}
}

if (a.length() == b.length())
{
// True or false doesn't really matter here, they are the same
return false;
}
else if (a.length() > b.length())
{
return isBefore(a.substr(b.length(), a.length() - b.length()), b);
}
else
{
return isBefore(a, b.substr(a.length(), b.length() - a.length()));
}
}

class Solution
{
public:
string largestNumber(vector<int> &num)
{
int n = num.size();
vector<string> nums;
vector<bool> free;

for (int i = 0; i < n; i++)
{
stringstream iss;
iss << num[i];
nums.push_back(iss.str());
free.push_back(true);
}

sort(nums.begin(), nums.end(), isBefore);

stringstream oss;
for (int i = 0; i < n; i++)
{
oss << nums[i];
}

string s = oss.str();

if (s[0] == '0')
{
return "0";
}
else
{
return s;
}
}
};
};

using namespace _LEET_LARGEST_NUMBER;

int LEET_LARGEST_NUMBER()
{
Solution solution;
int data[] = {3, 30, 34, 5, 9};
vector<int> input (data, data + sizeof(data) / sizeof(data[0]) );
cout << solution.largestNumber(input) << endl;
return 0;
}