algorithm - 给一个文本 block ，一些快捷键和目标文本，如何获得最少的按键来转换文本？

Question

假设我有一些文本(代码):

  def text = ParamMenuable.this.linkText
  def locPath: List[LocPath] = ParamMenuable.this.path
  def parser = ParamMenuable.this.parser
  def listToFrom(in: List[String]): Box[String] = in.headOption

还有一些快捷键:

arrow-left/right/up/down:  move cursor to left/right/up/down for one char

ctrl + d: duplicate current line
ctrl + arrow-left/right/up/down:  move cursor to left/right/up/down for one word
ctrl + y: delete current line
... all kinds of key shorts you usually used

目标文本是:

  def text() = {
     ParamMenuable.this.linkText
  }
  def locPath: List[LocPath] = ParamMenuable.this.path
  def locPath22222: List[LocPath] = ParamMenuable.this.path
  private def parser = {
      return ParamMenuable.this.parser;
  }

我的问题是:将源文本转换为目标文本至少应该按下多少键？您可以选择合适的 key 短裤来做得更好。

Answer 1

这可能是 NP 难的。 This paper为编辑器提供了一个硬性证明，其中插入、删除和子字符串移动都具有恒定的成本。

%0 Book Section
%D 2002
%@ 978-3-540-43862-5
%B Combinatorial Pattern Matching
%V 2373
%S Lecture Notes in Computer Science
%E Apostolico, Alberto
%E Takeda, Masayuki
%R 10.1007/3-540-45452-7_9
%T Edit Distance with Move Operations
%U http://dx.doi.org/10.1007/3-540-45452-7_9
%I Springer Berlin Heidelberg
%8 2002-01-01
%A Shapira, Dana
%A Storer, JamesA.
%P 85-98
%G English