logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
刚做了一道题挺有意思
avatar
刚做了一道题挺有意思# JobHunting - 待字闺中
p*2
1 楼
有两个字符串s 和 u， 问最少的步数从s转换倒u。
转换的方法，
从s任意取一个substring，然后可以执行以下三种操作
Insert one letter to any end of the string.
Delete one letter from any end of the string.
Change one letter into any other one.
也就是说从s找一个substring，使得以上三种操作的步数最小，转换倒u。
avatar
d*w
2 楼
是计算两个单词的编辑距离吧，动态规划，构造2维矩阵d[m][n],初始为0。
if s[i] = t[j] then
d[i, j] := d[i-1, j-1] // no operation required
else
d[i, j] := minimum
(
d[i-1, j] + 1, // a deletion
d[i, j-1] + 1, // an insertion
d[i-1, j-1] + 1 // a substitution
)
还有个单词纠错的很类似，你看看呢？
http://www.justin.tv/problems/spellcheck

【在 p*****2 的大作中提到】
: 有两个字符串s 和 u， 问最少的步数从s转换倒u。
: 转换的方法，
: 从s任意取一个substring，然后可以执行以下三种操作
: Insert one letter to any end of the string.
: Delete one letter from any end of the string.
: Change one letter into any other one.
: 也就是说从s找一个substring，使得以上三种操作的步数最小，转换倒u。
avatar
v*a
3 楼
如果没理解错的话，先求LongestCommonSubstring
Answer = |u| - |LongestCommonSubstring|

【在 p*****2 的大作中提到】
: 有两个字符串s 和 u， 问最少的步数从s转换倒u。
: 转换的方法，
: 从s任意取一个substring，然后可以执行以下三种操作
: Insert one letter to any end of the string.
: Delete one letter from any end of the string.
: Change one letter into any other one.
: 也就是说从s找一个substring，使得以上三种操作的步数最小，转换倒u。
avatar
d*w
4 楼
不好意思，没看清题意。

【在 d********w 的大作中提到】
: 是计算两个单词的编辑距离吧，动态规划，构造2维矩阵d[m][n],初始为0。
: if s[i] = t[j] then
: d[i, j] := d[i-1, j-1] // no operation required
: else
: d[i, j] := minimum
: (
: d[i-1, j] + 1, // a deletion
: d[i, j-1] + 1, // an insertion
: d[i-1, j-1] + 1 // a substitution
: )
avatar
p*2
5 楼

大牛啥时候入职呀。

【在 v***a 的大作中提到】
: 如果没理解错的话，先求LongestCommonSubstring
: Answer = |u| - |LongestCommonSubstring|
avatar
p*2
6 楼

不一定是commonsubstring, 中间的字符可以替换。
比如
aabgccc 找 bec
就是一次。
bgc->bec
但是他们的common substring 是 b 或 c

【在 v***a 的大作中提到】
: 如果没理解错的话，先求LongestCommonSubstring
: Answer = |u| - |LongestCommonSubstring|
avatar
p*2
7 楼
这是我的代码。
public class test
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
String s=in.next();
String u=in.next();

int row=u.length();
int col=s.length();

boolean[][] matrix=new boolean[row][col];

for(int i=0;i{
char c=u.charAt(i);
for(int j=0;jif(s.charAt(j)==c)
matrix[i][j]=true;
}

int min=u.length();

for(int i=0;i{
if(i>min)
break;

for(int j=0;j{
if(matrix[i][j])
{
int x=i+1;
int y=j+1;
int count=1;
while(x{
if(matrix[x][y])
{
count++;
matrix[x][y]=false;
}

x++;
y++;

}

min=Math.min(min,u.length()-count);
matrix[i][j]=false;
}
}
}

System.out.println(min);

}
}
avatar
l*i
9 楼
CF problem A.
Your solution is a good one. the problem makes insert/delete unnecessary,
since it can always be simulated with one change with same penalty.
avatar
p*2
10 楼

insert还是需要的吧？
比如
abcde
def
就需要插入。

【在 l***i 的大作中提到】
: CF problem A.
: Your solution is a good one. the problem makes insert/delete unnecessary,
: since it can always be simulated with one change with same penalty.
avatar
v*a
11 楼
懂了，那插入和删除就没有意义了，直接替换就是了

【在 p*****2 的大作中提到】
:
: insert还是需要的吧？
: 比如
: abcde
: def
: 就需要插入。
avatar
p*2
12 楼

insert还是需要的吧？
比如
abcde
def
就需要插入。

【在 v***a 的大作中提到】
: 懂了，那插入和删除就没有意义了，直接替换就是了
avatar
L*k
13 楼
有意思的题目，有点research的味道

【在 p*****2 的大作中提到】
: 有两个字符串s 和 u， 问最少的步数从s转换倒u。
: 转换的方法，
: 从s任意取一个substring，然后可以执行以下三种操作
: Insert one letter to any end of the string.
: Delete one letter from any end of the string.
: Change one letter into any other one.
: 也就是说从s找一个substring，使得以上三种操作的步数最小，转换倒u。
avatar
c*e
14 楼
不是两个单词的距离，因为原题说可以substring的。

【在 d********w 的大作中提到】
: 是计算两个单词的编辑距离吧，动态规划，构造2维矩阵d[m][n],初始为0。
: if s[i] = t[j] then
: d[i, j] := d[i-1, j-1] // no operation required
: else
: d[i, j] := minimum
: (
: d[i-1, j] + 1, // a deletion
: d[i, j-1] + 1, // an insertion
: d[i-1, j-1] + 1 // a substitution
: )
avatar
c*p
15 楼
我觉得就是字符串的匹配问题吧。 用u匹配s的每个等长字串，看看有多少个字符不同
。考虑到u的开始和结束的特殊情况，可以在u的前后加上足够的pad.
#include
#include
using namespace std;
const char PAD = '$';
int match(string p, string q, size_t len)
{
int count = 0;
for(size_t i = 0; i < len; i++){
if (p.at(i) != q.at(i)){
count++;
}
}
return count;
}
size_t edit (string from, string to, string& sub)
{
string pad;
pad.append( to.length()-1, PAD);
from = pad+from+pad;
int count = INT_MAX;
for (size_t i = 0; i <= from.length() - to.length(); i++ ){
string str = from.substr(i, to.length());
int cur = match(str, to, to.length());
if (cur < count){
count = cur;
sub = str;
}
}
while(sub.at(sub.length()-1) == PAD ){
sub = sub.substr(0, sub.length()-1);
}
while(sub.at(0) == PAD ){
sub = sub.substr(1, sub.length()-1);
}
return count;
}
int main() {
string a ="aabgccc";
string b = "bec";
string sub;
cout << "a=" << a <"; substring =" << sub << endl;
return 0;
}

【在 p*****2 的大作中提到】
: 有两个字符串s 和 u， 问最少的步数从s转换倒u。
: 转换的方法，
: 从s任意取一个substring，然后可以执行以下三种操作
: Insert one letter to any end of the string.
: Delete one letter from any end of the string.
: Change one letter into any other one.
: 也就是说从s找一个substring，使得以上三种操作的步数最小，转换倒u。
avatar
p*2
16 楼
有两个字符串s 和 u， 问最少的步数从s转换倒u。
转换的方法，
从s任意取一个substring，然后可以执行以下三种操作
Insert one letter to any end of the string.
Delete one letter from any end of the string.
Change one letter into any other one.
也就是说从s找一个substring，使得以上三种操作的步数最小，转换倒u。
更新：F跟这题还不一样。F的就是edit distance+some misleading informaiton
avatar
d*w
17 楼
是计算两个单词的编辑距离吧，动态规划，构造2维矩阵d[m][n],初始为0。
if s[i] = t[j] then
d[i, j] := d[i-1, j-1] // no operation required
else
d[i, j] := minimum
(
d[i-1, j] + 1, // a deletion
d[i, j-1] + 1, // an insertion
d[i-1, j-1] + 1 // a substitution
)
还有个单词纠错的很类似，你看看呢？
http://www.justin.tv/problems/spellcheck

【在 p*****2 的大作中提到】
: 有两个字符串s 和 u， 问最少的步数从s转换倒u。
: 转换的方法，
: 从s任意取一个substring，然后可以执行以下三种操作
: Insert one letter to any end of the string.
: Delete one letter from any end of the string.
: Change one letter into any other one.
: 也就是说从s找一个substring，使得以上三种操作的步数最小，转换倒u。
: 更新：F跟这题还不一样。F的就是edit distance+some misleading informaiton
avatar
v*a
18 楼
如果没理解错的话，先求LongestCommonSubstring
Answer = |u| - |LongestCommonSubstring|

【在 p*****2 的大作中提到】
: 有两个字符串s 和 u， 问最少的步数从s转换倒u。
: 转换的方法，
: 从s任意取一个substring，然后可以执行以下三种操作
: Insert one letter to any end of the string.
: Delete one letter from any end of the string.
: Change one letter into any other one.
: 也就是说从s找一个substring，使得以上三种操作的步数最小，转换倒u。
: 更新：F跟这题还不一样。F的就是edit distance+some misleading informaiton
avatar
d*w
19 楼
不好意思，没看清题意。

【在 d********w 的大作中提到】
: 是计算两个单词的编辑距离吧，动态规划，构造2维矩阵d[m][n],初始为0。
: if s[i] = t[j] then
: d[i, j] := d[i-1, j-1] // no operation required
: else
: d[i, j] := minimum
: (
: d[i-1, j] + 1, // a deletion
: d[i, j-1] + 1, // an insertion
: d[i-1, j-1] + 1 // a substitution
: )
avatar
p*2
20 楼

大牛啥时候入职呀。

【在 v***a 的大作中提到】
: 如果没理解错的话，先求LongestCommonSubstring
: Answer = |u| - |LongestCommonSubstring|
avatar
p*2
21 楼

不一定是commonsubstring, 中间的字符可以替换。
比如
aabgccc 找 bec
就是一次。
bgc->bec
但是他们的common substring 是 b 或 c

【在 v***a 的大作中提到】
: 如果没理解错的话，先求LongestCommonSubstring
: Answer = |u| - |LongestCommonSubstring|
avatar
p*2
22 楼
这是我的代码。
public class test
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
String s=in.next();
String u=in.next();

int row=u.length();
int col=s.length();

boolean[][] matrix=new boolean[row][col];

for(int i=0;i{
char c=u.charAt(i);
for(int j=0;j if(s.charAt(j)==c)
matrix[i][j]=true;
}

int min=u.length();

for(int i=0;i{
if(i>min)
break;

for(int j=0;j{
if(matrix[i][j])
{
int x=i+1;
int y=j+1;
int count=1;
while(x{
if(matrix[x][y])
{
count++;
matrix[x][y]=false;
}

x++;
y++;

}

min=Math.min(min,u.length()-count);
matrix[i][j]=false;
}
}
}

System.out.println(min);

}
}
avatar
l*i
24 楼
CF problem A.
Your solution is a good one. the problem makes insert/delete unnecessary,
since it can always be simulated with one change with same penalty.
avatar
p*2
25 楼

insert还是需要的吧？
比如
abcde
def
就需要插入。

【在 l***i 的大作中提到】
: CF problem A.
: Your solution is a good one. the problem makes insert/delete unnecessary,
: since it can always be simulated with one change with same penalty.
avatar
v*a
26 楼
懂了，那插入和删除就没有意义了，直接替换就是了

【在 p*****2 的大作中提到】
:
: insert还是需要的吧？
: 比如
: abcde
: def
: 就需要插入。
avatar
p*2
27 楼

insert还是需要的吧？
比如
abcde
def
就需要插入。

【在 v***a 的大作中提到】
: 懂了，那插入和删除就没有意义了，直接替换就是了
avatar
L*k
28 楼
有意思的题目，有点research的味道

【在 p*****2 的大作中提到】
: 有两个字符串s 和 u， 问最少的步数从s转换倒u。
: 转换的方法，
: 从s任意取一个substring，然后可以执行以下三种操作
: Insert one letter to any end of the string.
: Delete one letter from any end of the string.
: Change one letter into any other one.
: 也就是说从s找一个substring，使得以上三种操作的步数最小，转换倒u。
: 更新：F跟这题还不一样。F的就是edit distance+some misleading informaiton
avatar
c*e
29 楼
不是两个单词的距离，因为原题说可以substring的。

【在 d********w 的大作中提到】
: 是计算两个单词的编辑距离吧，动态规划，构造2维矩阵d[m][n],初始为0。
: if s[i] = t[j] then
: d[i, j] := d[i-1, j-1] // no operation required
: else
: d[i, j] := minimum
: (
: d[i-1, j] + 1, // a deletion
: d[i, j-1] + 1, // an insertion
: d[i-1, j-1] + 1 // a substitution
: )
avatar
c*p
30 楼
我觉得就是字符串的匹配问题吧。 用u匹配s的每个等长字串，看看有多少个字符不同
。考虑到u的开始和结束的特殊情况，可以在u的前后加上足够的pad.
#include
#include
using namespace std;
const char PAD = '$';
int match(string p, string q, size_t len)
{
int count = 0;
for(size_t i = 0; i < len; i++){
if (p.at(i) != q.at(i)){
count++;
}
}
return count;
}
size_t edit (string from, string to, string& sub)
{
string pad;
pad.append( to.length()-1, PAD);
from = pad+from+pad;
int count = INT_MAX;
for (size_t i = 0; i <= from.length() - to.length(); i++ ){
string str = from.substr(i, to.length());
int cur = match(str, to, to.length());
if (cur < count){
count = cur;
sub = str;
}
}
while(sub.at(sub.length()-1) == PAD ){
sub = sub.substr(0, sub.length()-1);
}
while(sub.at(0) == PAD ){
sub = sub.substr(1, sub.length()-1);
}
return count;
}
int main() {
string a ="aabgccc";
string b = "bec";
string sub;
cout << "a=" << a <"; substring =" << sub << endl;
return 0;
}

【在 p*****2 的大作中提到】
: 有两个字符串s 和 u， 问最少的步数从s转换倒u。
: 转换的方法，
: 从s任意取一个substring，然后可以执行以下三种操作
: Insert one letter to any end of the string.
: Delete one letter from any end of the string.
: Change one letter into any other one.
: 也就是说从s找一个substring，使得以上三种操作的步数最小，转换倒u。
: 更新：F跟这题还不一样。F的就是edit distance+some misleading informaiton
avatar
p*2
31 楼
更新一下。
avatar
w*y
32 楼
没看太懂, 感觉是找一个substringof s, 使得该substring跟u的edit distance最小?
avatar
a*g
33 楼
赞

【在 c***p 的大作中提到】
: 我觉得就是字符串的匹配问题吧。 用u匹配s的每个等长字串，看看有多少个字符不同
: 。考虑到u的开始和结束的特殊情况，可以在u的前后加上足够的pad.
: #include
: #include
: using namespace std;
: const char PAD = '$';
: int match(string p, string q, size_t len)
: {
: int count = 0;
: for(size_t i = 0; i < len; i++){
avatar
p*n
35 楼
C版

／＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊／
int match (const char *s1, const char *s2, const int len) {
int r = 0;
for (int i = 0; i < len; i++)
if (*(s1+i) == *(s2+i))
r++;
return r;
}
size_t edit (const char *s, const char *u, int *begin, int *end) {
size_t maxmatch = 0;
for (int i = 0, j = strlen(u)-1; i < strlen(s); (j > 0)?j--:i++) {
int len = min(strlen(u) - j, strlen(s) - i);
int m = match(s+i, u+j, len);
if (m > maxmatch) {
maxmatch = m;
*begin = i;
*end = i + len - 1;
}
}
return strlen(u) - maxmatch;
}
int main() {
const char *pa = "aabgccc";
const char *pb = "bec";
int strB = 0, strE = 0;
printf("a=%s; b=%s; edit cost =%zu; substring =", pa, pb, edit(pa, pb, &
strB, &strE));
for (int i = strB; i <= strE; i++)
printf("%c", pa[i]);
printf("\n");
return 0;
}

【在 c***p 的大作中提到】
: 我觉得就是字符串的匹配问题吧。 用u匹配s的每个等长字串，看看有多少个字符不同
: 。考虑到u的开始和结束的特殊情况，可以在u的前后加上足够的pad.
: #include
: #include
: using namespace std;
: const char PAD = '$';
: int match(string p, string q, size_t len)
: {
: int count = 0;
: for(size_t i = 0; i < len; i++){
相关阅读
打算明年八月份phd毕业， 一般什么时候开始找工作比较合适呢，谢谢。面了一个contract职位background 能知道过去的salary多少吗？local小公司面试，什么衣服合适？G家的题目有人做出来了吗？C++ Q88: nested non-template class关于Java Software Structures: Designing and Using Data Structures一本用Java进行算法面试的好书A Google Problem (2)学经济的在湾区好找工作些还是西雅图？HR　打电话问了个问题后就没消息是怎么回事？电面结束了，有被欺骗的感觉。同时求助----我现在的情况怎么办？问个google面试题网申状态显示route是什么意思请教关于GE position的title诚心求数字 IC 职位内推 (Verilog / RTL design)新单位报到有不少公司要网上填简历申请很繁琐looking for java developer with >5 years experiences (转载)job description上有几条要求不符合
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。