b*****p
发帖数: 9649 | 1 Previous discussions are available
1. Studious Student Problem Analysis
http://www.ihas1337code.com/2011/01/studious-student-problem-an
2. http://www.mitbbs.com/article_t/Programming/31179801.html
"i has 1337 code" gave a very good sample to explain why the simple sorting
of strings won't work in his port.
The most brilliant and 'SIMPLE' solution is from blaze and "i has 1337 code"
Saying it is 'SIMPLE' because the code is so elegant/short but the most
interesting part is to prove this solution like blaze mentioned in his posts.
Here is my proof.
Before we jump to the formal proof. Let us play with some simple cases.
suppose we have a series of characters:a,b,c,d which satisfy the criteria
mentioned in the solution.
That is: a < b < c < d; therefore we have
ab < ba, ac < ca, ad < da, bc < cb, ...
let us compare cba and abc.
cba
> cab (fix c, exchange a and b, and ba>ab)
> acb (fix b, exchange a and c, and ca>ac)
> abc (fix a, exchange b and c, and cb>bc)
so, we have cba > abc
compare abcd and dbca [the pattern, if you already notice, is I exchange 'a'
(first) with 'd'(last) in the abcd ]
it is almost the same:
dbca
> dbac (fix db, exchange a,c, ca>ac )
> dabc (fix d and c, exchange a,b, ba>ab)
> adbc (fix bc, exchange a,d, db>bd)
> abdc (fix a and c, exchange b,d, db>bd)
> abcd (fix ab, exchange c,d, dc>cd)
the trick is to exchange one pair at a time:
the element 'a' moves from last potion to first position and then move the
element 'd' down from first position to last position.
Then we can conclude a general format
x {Z} y < y {Z} x, if x < y and {Z} is in order. ---> C1
(the proof is straighforward by using the tricky mentioned above)
Now we prove the solution. We use proof of contradiction.
Given the minimum solution X, we prove that there is no single such
pair of x[i], x[j] that x[i] > x[j] and i < j.
Proof by contradiction:
Suppose we have one of such a pair of x[i], x[j], and others are in order
then if we can construct a new solution X' based on X and X' < X, then we
lead to a contradiction : X is not the minimum. This will prove that the
minimum must be kept
in the order.
Obviously, we can construct X' by switching x[i], x[j] in X.
the new solution X' will look like
X' = x[0]..x[i-1] x[j] x[i+1]..x[j-1] x[i] x[j+1]...x[n]
where
X = x[0]..x[i-1] x[i] x[i+1]..x[j-1] x[j] x[j+1]...x[n]
Comparing X and X', they have the same prefix (x[0..i-1]) and suffix(x[j+1..
n]).
We do not need to consider them. The most interesting part is
in X', Y'= x[j]x[i+1]...x[j-1]x[i]
in X, Y = x[i]x[i+1]...x[j-1]x[j]
Notice that we already prove Y' < Y in C1. Therefore X'
solution. | i**********e
发帖数: 1145 | 2 BTW, for people who had not seen this problem, here is the problem
description:
Given a list of strings, find a concatenation of all the strings such that
its dictionary order is the smallest among all the possibilities.
For instance, by joining the list ["ab", "cd", "ef"] we can get:
"abcdef",
"cdabef",
"cdefab",
..., ...
where "abcdef" is the one of the least dictionary order.
Thanks for your post. I believe my thought process is similar to yours. Here
are some of my notes that help me in "visualizing" the solution (with some
concrete examples).
Notes:
1) It is easy to observe that if all words in the list are of equal length,
then sorting + concatenate must yield the smallest dictionary order.
2) However, if any word appears to be a prefix of one or more other words,
then sorting + concatenate does not necessarily yield the smallest
dictionary order. For example, the list is ["ji" "jib"], then sorting +
concatenate yields "jijib", while the correct answer should be "jibji".
3) To solve this problem correctly, we must also solve the special case
where a word appears as a prefix in other words.
4) One easy solution (non-trivial to prove, but easy to reason), is to
define the order relation where s1 is less than s2 if and only if s1+s2
s1.
5) Here is a concrete example why this works. Define a list as ["ji" "jibw"
"jijibw"]
6) By the definition of s1+s2
in the list is "jibw". This is because "jibwji" < "jijibw" and "jibwjijibw"
< "jijibwjibw".
7) Now, the key to understand why s1+s2
order is: we have found the smallest word such that s1+x < x+s1. Therefore,
it is impossible to swap the words to yield a smaller dictionary order. For
a case with more words, then this order relation holds: s1+x < x+s1, and x+
y < y+x. As swapping at any point could not yield a smaller dictionary order
, therefore s1+x+y must yield the smallest dictionary order. This can be
generalized to all N words by induction.
8) I believe 7) is the transition property that blaze had mentioned which is
important in the proof of correctness. I do not claim that this is a rigid
or even a correctly constructed proof. However, it does help me in
convincing myself this is a valid solution.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | j********x
发帖数: 2330 | 3 very interesting, thanks for sharing!~ | Z*****Z
发帖数: 723 | 4 上来赞一下偶像。这个题看了楼主和偶像的帖子，很受启发。我再从一个略微不同的角
度分析一下。
可以这样想，给了一组string，需要最后合并成一个string，那么排第一的究竟是那个
？
假设所有的string都是由小写的英文字母构成，那么可以按照首字母将所有string分成
最多26组。
1。 如果以a开头的那组不空，一定一定是其中的某一个string排在第一。否则，考察以
b开头的那一组，以此类推。
2。不妨假设所有单词都以b开头。那么这些单词之中那个排在第一呢？显然，如果所有
单词的长度都不小于2的话，那么我们可以按照第二个字母再将所有的单词分成26组，这
就回到了步骤1。
3。特殊的情况就在于有些单词长度不够了（这也就是所谓的一个string是另一个strin
g的前缀的情况），这时如何排序。
只需要考虑四个典型string：b，ba，bb，bc，这已经代表了所有的可能性。为了更加清
晰，我用$表示一个string的结尾。也就是说，有这样4个string：b$, ba$, bb$, bc$
在字典排序里，这个结尾的$是排在所有的字母之前的。但是偶像已经说了，在这个题目
里不是这样的。
4。一个很显然的事实就是我们仍然有 ba$ < bb$
5。不妨考虑b$和ba$，两种排序的结果是：
(1)b$ba$
(2)ba$b$
如果这个$符号真的能够占据一个字符的位置的话，那么显然b$应该排在ba$前面。常理
上的字典排序仍然成立。不行的是$符号不占位置，所以上面两种排序得到的结果实际是
：
(1')bba
(2')bab
请注意情况(1)里面的第一个$被它后面的字符b给替换掉了。这就提示我们应该先做替换
，再做比较。
6。根据上一步，两个string，s1和s2比较，
（1）如果一个是另外一个的前缀，不妨设s1是s2的前缀，设两个string的长
度分别为
L1和L2，那么实际需要比较的就是s2和s1s2的前L2个字母。
（2）否则，直接用一般的方法比较。
7。进一步推广，两个长度不一样的string比较，把长的先接在短的后面，然后再用一般
的字典排序比较。如此选出来的string，必然是排在第一个的。
8。如果再推广的话，就是像偶像说的，互相接起来，（这样长度必然相同，）再比。
这个题目是贪心，不是DP。
【在 i**********e 的大作中提到】
: BTW, for people who had not seen this problem, here is the problem
: description:
: Given a list of strings, find a concatenation of all the strings such that
: its dictionary order is the smallest among all the possibilities.
: For instance, by joining the list ["ab", "cd", "ef"] we can get:
: "abcdef",
: "cdabef",
: "cdefab",
: ..., ...
: where "abcdef" is the one of the least dictionary order.
| b*****p
发帖数: 9649 | |
|
